diff options
Diffstat (limited to 'slib.texi')
| -rw-r--r-- | slib.texi | 9058 |
1 files changed, 9058 insertions, 0 deletions
diff --git a/slib.texi b/slib.texi new file mode 100644 index 0000000..1d41fdc --- /dev/null +++ b/slib.texi @@ -0,0 +1,9058 @@ +\input texinfo @c -*-texinfo-*- +@c %**start of header +@setfilename slib.info +@settitle SLIB +@setchapternewpage on +@c Choices for setchapternewpage are {on,off,odd}. +@paragraphindent 2 +@c %**end of header + +@iftex +@finalout +@c DL: lose the egregious vertical whitespace, esp. around examples +@c but paras in @defun-like things don't have parindent +@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 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 + +@titlepage +@title SLIB +@subtitle The Portable Scheme Library +@subtitle Version 2a3 +@subtitle June 1995 +@author by Todd R. Eigenschink, Dave Love, and Aubrey Jaffer + +@page +@vskip 0pt plus 1filll +Copyright @copyright{} 1993, 1994, 1995 Todd R. Eigenschink and 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. +@end titlepage + + + + + +@node Top, Overview, (dir), (dir) + +@ifinfo +This file documents SLIB, the portable Scheme library. + +@heading Good Engineering is 1% inspiration and 99% documentation. + +Herein lies the good part. Many thanks to Todd Eigenschink +<eigenstr@@CS.Rose-Hulman.Edu> (who thanks Dave Love <D.Love@@dl.ac.uk>) +for creating @file{slib.texi}. I have learned much from their example. + +Aubrey Jaffer +jaffer@@ai.mit.edu +@end ifinfo + + +@menu +* Overview:: What is SLIB? + +* Data Structures:: Various data structures. +* Macros:: Extensions to Scheme syntax. +* Numerics:: +* Procedures:: Miscellaneous utility procedures. +* Standards Support:: Support for Scheme Standards. +* Session Support:: Debugging, Pathnames, Require, etc. + +* Optional SLIB Packages:: +* Procedure and Macro Index:: +* Variable Index:: +@end menu + + +@node Overview, Data Structures, Top, Top +@chapter Overview + +SLIB is a portable Scheme library meant to provide compatibility and +utility functions for all standard Scheme implementations, and fixes +several implementations which are non-conforming. SLIB conforms to +@cite{Revised^4 Report on the Algorithmic Language Scheme} and the IEEE +P1178 specification. SLIB supports Unix and similar systems, VMS, and +MS-DOS.@refill + +For a summary of what each file contains, see the file @file{README}. +For a list of the features that have changed since the last SLIB +release, see the file @file{ANNOUNCE}. For a list of the features that +have changed over time, see the file @file{ChangeLog}. + +The maintainer can be reached as @samp{jaffer@@ai.mit.edu}. + +@menu +* Installation:: How to install SLIB on your system. +* Porting:: SLIB to new platforms +* Coding Standards:: How to write modules for SLIB. +* Copyrights:: Intellectual propery issues. +* Manual Conventions:: Conventions used in this manual. +@end menu + +@node Installation, Porting, Overview, Overview +@section Installation + +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. + +If the Scheme implementation supports @code{getenv}, then the value of +the shell environment variable @var{SCHEME_LIBRARY_PATH} will be used +for @code{(library-vicinity)} if it is defined. Currently, Chez, Elk, +MITScheme, scheme->c, VSCM, and SCM support @code{getenv}. + +You should check the definitions of @code{software-type}, +@code{scheme-implementation-version}, +@iftex +@* +@end iftex +@code{implementation-vicinity}, +and @code{library-vicinity} in the initialization file. There are +comments in the file for how to configure it. + +Once this is done you can modify the startup file for your Scheme +implementation to @code{load} this initialization file. SLIB is then +installed. + +Multiple implementations of Scheme can all use the same SLIB directory. +Simply configure each implementation's initialization file as outlined +above. + +The SCM implementation does not require any initialization file as SLIB +support is already built in to SCM. See the documentation with SCM for +installation instructions. + +SLIB includes methods to create heap images for the VSCM and Scheme48 +implementations. The instructions for creating a VSCM image are in +comments in @file{vscm.init}. To make a Scheme48 image, @code{cd} to +the SLIB directory and type @code{make slib48}. This will also create a +shell script with the name @code{slib48} which will invoke the saved +image. + +@node Porting, Coding Standards, Installation, Overview +@section Porting + +If there is no initialization file for your Scheme implementation, you +will have to create one. Your Scheme implementation must be largely +compliant with @cite{IEEE Std 1178-1990} or @cite{Revised^4 Report on +the Algorithmic Language Scheme} to support SLIB. + +@file{Template.scm} is an example configuration file. The comments +inside will direct you on how to customize it to reflect your system. +Give your new initialization file the implementation's name with +@file{.init} appended. For instance, if you were porting +@code{foo-scheme} then the initialization file might be called +@file{foo.init}. + +Your customized version should then be loaded as part of your scheme +implementation's initialization. It will load @file{require.scm} +(@xref{Require}) from the library; this will allow the use of +@code{provide}, @code{provided?}, and @code{require} along with the +@dfn{vicinity} functions (@code{vicinity} functions are documented in +the section on Require. @xref{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} +so that they can be included in the SLIB distribution.@refill + +@node Coding Standards, Copyrights, Porting, Overview +@section Coding Standards + +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 + +@file{require.scm} defines @code{*catalog*}, an association list of +module names and filenames. When a new package is added to the library, +an entry should be added to @file{require.scm}. Local packages can also +be added to @code{*catalog*} and even shadow entries already in the +table.@refill + +The module name and @samp{:} should prefix each symbol defined in the +package. Definitions for external use should then be exported by having +@code{(define foo module-name:foo)}.@refill + +Submitted code should not duplicate routines which are already in SLIB +files. Use @code{require} to force those features to be supported in +your package. Care should be taken that there are no circularities in +the @code{require}s and @code{load}s between the library +packages.@refill + +Documentation should be provided in Emacs Texinfo format if possible, +But documentation must be provided. + +Your package will be released sooner with SLIB if you send me a file +which tests your code. Please run this test @emph{before} you send me +the code! + +@subheading Modifications + +Please document your changes. A line or two for @file{ChangeLog} is +sufficient for simple fixes or extensions. Look at the format of +@file{ChangeLog} to see what information is desired. Please send me +@code{diff} files from the latest SLIB distribution (remember to send +@code{diff}s of @file{slib.texi} and @file{ChangeLog}). This makes for +less email traffic and makes it easier for me to integrate when more +than one person is changing a file (this happens a lot with +@file{slib.texi} and @samp{*.init} files). + +If someone else wrote a package you want to significantly modify, please +try to contact the author, who may be working on a new version. This +will insure against wasting effort on obsolete versions. + +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, Manual Conventions, Coding Standards, Overview +@section Copyrights + +This section has instructions for SLIB authors regarding copyrights. + +Each package in SLIB must either be in the public domain, or come with a +statement of terms permitting users to copy, redistribute and modify it. +The comments at the beginning of @file{require.scm} and +@file{macwork.scm} illustrate copyright and appropriate terms. + +If your code or changes amount to less than about 10 lines, you do not +need to add your copyright or send a disclaimer. + +@subheading Putting code into the Public Domain + +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. + +@quotation +I, @var{name}, hereby affirm that I have placed the software package +@var{name} in the public domain. + +I affirm that I am the sole author and sole copyright holder for the +software package, that I have the right to place this software package +in the public domain, and that I will do nothing to undermine this +status in the future. + +@flushright + @var{signature and date} +@end flushright +@end quotation + +This wording assumes that you are the sole author. If you are not the +sole author, the wording needs to be different. If you don't want to be +bothered with sending a letter every time you release or modify a +module, make your letter say that it also applies to your future +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 +disclaimer to. An example disclaimer follows. + +@subheading Explicit copying terms + +@noindent +If you submit more than about 10 lines of code which you are not placing +into the Public Domain (by sending me a disclaimer) you need to: + +@itemize @bullet +@item +Arrange that your name appears in a copyright line for the appropriate +year. Multiple copyright lines are acceptable. +@item +With your copyright line, specify any terms you require to be different +from those already in the file. +@item +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 +disclaimer to. +@end itemize + +@subheading Example: Company Copyright Disclaimer + +This disclaimer should be signed by a vice president or general manager +of the company. If you can't get at them, anyone else authorized to +license out software produced there will do. Here is a sample wording: + +@quotation +@var{employer} Corporation hereby disclaims all copyright +interest in the program @var{program} written by @var{name}. + +@var{employer} Corporation affirms that it has no other intellectual +property interest that would undermine this release, and will do nothing +to undermine it in the future. + +@flushleft +@var{signature and date}, +@var{name}, @var{title}, @var{employer} Corporation +@end flushleft +@end quotation + +@node Manual Conventions, , Copyrights, Overview +@section Manual Conventions + +Things that are labeled as Functions are called for their return values. +Things that are labeled as Procedures are called primarily for their +side effects. + +All examples throughout this text were produced using the @code{scm} +Scheme implementation. + +At the beginning of each section, there is a line that looks something +like + +@code{(require 'feature)}. + +@noindent +This means that, in order to use @code{feature}, you must include the +line @code{(require 'feature)} somewhere in your code prior to the use +of that feature. @code{require} will make sure that the feature is +loaded.@refill + + + + + +@node Data Structures, Macros, Overview, Top +@chapter Data Structures + + + +@menu +* Arrays:: 'array +* Array Mapping:: 'array-for-each +* Association Lists:: 'alist +* Collections:: 'collect +* Dynamic Data Type:: 'dynamic +* Hash Tables:: 'hash-table +* Hashing:: 'hash, 'sierpinski, 'soundex +* Chapter Ordering:: 'chapter-order +* Object:: 'object +* Parameter lists:: 'parameters +* Priority Queues:: 'priority-queue +* Queues:: 'queue +* Records:: 'record +* Base Table:: +* Relational Database:: 'relational-database +* Weight-Balanced Trees:: 'wt-tree +* Structures:: 'struct, 'structure +@end menu + + + + +@node Arrays, Array Mapping, Data Structures, Data Structures +@section Arrays + +@code{(require 'array)} + +@defun array? obj +Returns @code{#t} if the @var{obj} is an array, and @code{#f} if not. +@end defun + +@defun make-array initial-value bound1 bound2 @dots{} +Creates and returns an array that has as many dimensins as there are +@var{bound}s and fills it with @var{initial-value}.@refill +@end defun + +When constructing an array, @var{bound} is either an inclusive range of +indices expressed as a two element list, or an upper bound expressed as +a single integer. So@refill +@lisp +(make-array 'foo 3 3) @equiv{} (make-array 'foo '(0 2) '(0 2)) +@end lisp + +@defun make-shared-array array mapper bound1 bound2 @dots{} +@code{make-shared-array} can be used to create shared subarrays of other +arrays. The @var{mapper} is a function that translates coordinates in +the new array into coordinates in the old array. A @var{mapper} must be +linear, and its range must stay within the bounds of the old array, but +it can be otherwise arbitrary. A simple example:@refill +@lisp +(define fred (make-array #f 8 8)) +(define freds-diagonal + (make-shared-array fred (lambda (i) (list i i)) 8)) +(array-set! freds-diagonal 'foo 3) +(array-ref fred 3 3) + @result{} FOO +(define freds-center + (make-shared-array fred (lambda (i j) (list (+ 3 i) (+ 3 j))) + 2 2)) +(array-ref freds-center 0 0) + @result{} FOO +@end lisp +@end defun + +@defun array-rank obj +Returns the number of dimensions of @var{obj}. If @var{obj} is not an +array, 0 is returned. +@end defun + +@defun array-shape array +@code{array-shape} returns a list of inclusive bounds. So: +@lisp +(array-shape (make-array 'foo 3 5)) + @result{} ((0 2) (0 4)) +@end lisp +@end defun + +@defun array-dimensions array +@code{array-dimensions} is similar to @code{array-shape} but replaces +elements with a 0 minimum with one greater than the maximum. So: +@lisp +(array-dimensions (make-array 'foo 3 5)) + @result{} (3 5) +@end lisp +@end defun + +@deffn Procedure array-in-bounds? array index1 index2 @dots{} +Returns @code{#t} if its arguments would be acceptable to +@code{array-ref}. +@end deffn + +@defun array-ref array index1 index2 @dots{} +Returns the element at the @code{(@var{index1}, @var{index2})} element +in @var{array}.@refill +@end defun + +@deffn Procedure array-set! array new-value index1 index2 @dots{} +@end deffn + +@defun array-1d-ref array index +@defunx array-2d-ref array index index +@defunx array-3d-ref array index index index +@end defun + +@deffn Procedure array-1d-set! array new-value index +@deffnx Procedure array-2d-set! array new-value index index +@deffnx Procedure array-3d-set! array new-value index index index +@end deffn + +The functions are just fast versions of @code{array-ref} and +@code{array-set!} that take a fixed number of arguments, and perform no +bounds checking.@refill + +If you comment out the bounds checking code, this is about as efficient +as you could ask for without help from the compiler. + +An exercise left to the reader: implement the rest of APL. + + + +@node Array Mapping, Association Lists, Arrays, Data Structures +@section Array Mapping + +@code{(require 'array-for-each)} + +@defun array-map! array0 proc array1 @dots{} +@var{array1}, @dots{} must have the same number of dimensions as +@var{array0} and have a range for each index which includes the range +for the corresponding index in @var{array0}. @var{proc} is applied to +each tuple of elements of @var{array1} @dots{} and the result is stored +as the corresponding element in @var{array0}. The value returned is +unspecified. The order of application is unspecified. +@end defun + +@defun array-for-each @var{proc} @var{array0} @dots{} +@var{proc} is applied to each tuple of elements of @var{array0} @dots{} +in row-major order. The value returned is unspecified. +@end defun + +@defun array-indexes @var{array} +Returns an array of lists of indexes for @var{array} such that, if +@var{li} is a list of indexes for which @var{array} is defined, (equal? +@var{li} (apply array-ref (array-indexes @var{array}) @var{li})). +@end defun + +@defun array-copy! source destination +Copies every element from vector or array @var{source} to the +corresponding element of @var{destination}. @var{destination} must have +the same rank as @var{source}, and be at least as large in each +dimension. The order of copying is unspecified. +@end defun + + +@node Association Lists, Collections, Array Mapping, Data Structures +@section Association Lists + +@code{(require 'alist)} + +Alist functions provide utilities for treating a list of key-value pairs +as an associative database. These functions take an equality predicate, +@var{pred}, as an argument. This predicate should be repeatable, +symmetric, and transitive.@refill + +Alist functions can be used with a secondary index method such as hash +tables for improved performance. + +@defun predicate->asso pred +Returns an @dfn{association function} (like @code{assq}, @code{assv}, or +@code{assoc}) corresponding to @var{pred}. The returned function +returns a key-value pair whose key is @code{pred}-equal to its first +argument or @code{#f} if no key in the alist is @var{pred}-equal to the +first argument.@refill +@end defun + +@defun alist-inquirer pred +Returns a procedure of 2 arguments, @var{alist} and @var{key}, which +returns the value associated with @var{key} in @var{alist} or @code{#f} if +@var{key} does not appear in @var{alist}.@refill +@end defun + +@defun alist-associator pred +Returns a procedure of 3 arguments, @var{alist}, @var{key}, and +@var{value}, which returns an alist with @var{key} and @var{value} +associated. Any previous value associated with @var{key} will be +lost. This returned procedure may or may not have side effects on its +@var{alist} argument. An example of correct usage is:@refill +@lisp +(define put (alist-associator string-ci=?)) +(define alist '()) +(set! alist (put alist "Foo" 9)) +@end lisp +@end defun + +@defun alist-remover pred +Returns a procedure of 2 arguments, @var{alist} and @var{key}, which +returns an alist with an association whose @var{key} is key removed. +This returned procedure may or may not have side effects on its +@var{alist} argument. An example of correct usage is:@refill +@lisp +(define rem (alist-remover string-ci=?)) +(set! alist (rem alist "foo")) +@end lisp +@end defun + +@defun alist-map proc alist +Returns a new association list formed by mapping @var{proc} over the +keys and values of @var{alist}. @var{proc} must be a function of 2 +arguments which returns the new value part. +@end defun + +@defun alist-for-each proc alist +Applies @var{proc} to each pair of keys and values of @var{alist}. +@var{proc} must be a function of 2 arguments. The returned value is +unspecified. +@end defun + + +@node Collections, Dynamic Data Type, Association Lists, Data Structures +@section Collections + +@c Much of the documentation in this section was written by Dave Love +@c (d.love@dl.ac.uk) -- don't blame Ken Dickey for its faults. +@c but we can blame him for not writing it! + +@code{(require 'collect)} + +Routines for managing collections. Collections are aggregate data +structures supporting iteration over their elements, similar to the +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}). +They must support the following operations: +@itemize @bullet +@item +@code{(collection? @var{self})} (always returns @code{#t}); + +@item +@code{(size @var{self})} returns the number of elements in the collection; + +@item +@code{(print @var{self} @var{port})} is a specialized print operation +for the collection which prints a suitable representation on the given +@var{port} or returns it as a string if @var{port} is @code{#t};@refill + +@item +@code{(gen-elts @var{self})} returns a thunk which on successive +invocations yields elements of @var{self} in order or gives an error if +it is invoked more than @code{(size @var{self})} times;@refill + +@item +@code{(gen-keys @var{self})} is like @code{gen-elts}, but yields the +collection's keys in order. + +@end itemize +They might support specialized @code{for-each-key} and +@code{for-each-elt} operations.@refill + +@defun collection? obj +A predicate, true initially of lists, vectors and strings. New sorts of +collections must answer @code{#t} to @code{collection?}.@refill +@end defun + +@deffn Procedure map-elts proc . collections +@deffnx Procedure do-elts proc . collections +@var{proc} is a procedure taking as many arguments as there are +@var{collections} (at least one). The @var{collections} are iterated +over in their natural order and @var{proc} is applied to the elements +yielded by each iteration in turn. The order in which the arguments are +supplied corresponds to te order in which the @var{collections} appear. +@code{do-elts} is used when only side-effects of @var{proc} are of +interest and its return value is unspecified. @code{map-elts} returns a +collection (actually a vector) of the results of the applications of +@var{proc}.@refill + +Example: +@lisp +(map-elts + (list 1 2 3) (vector 1 2 3)) + @result{} #(2 4 6) +@end lisp +@end deffn + +@deffn Procedure map-keys proc . collections +@deffnx Procedure do-keys proc . collections +These are analogous to @code{map-elts} and @code{do-elts}, but each +iteration is over the @var{collections}' @emph{keys} rather than their +elements.@refill + +Example: +@lisp +(map-keys + (list 1 2 3) (vector 1 2 3)) + @result{} #(0 2 4) +@end lisp +@end deffn + +@deffn Procedure for-each-key collection proc +@deffnx Procedure for-each-elt collection proc +These are like @code{do-keys} and @code{do-elts} but only for a single +collection; they are potentially more efficient. +@end deffn + +@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 +list-based version if @code{(require 'collect)} follows @code{(require +'common-list-functions)} (@xref{Common List Functions}).@refill + +Examples: +@lisp +(reduce + 0 (vector 1 2 3)) + @result{} 6 +(reduce union '() '((a b c) (b c d) (d a))) + @result{} (c b d a). +@end lisp +@end defun + +@defun any? pred . collections +A generalization of the list-based @code{some} (@xref{Lists as +sequences}) to collections.@refill + +Example: +@lisp +(any? odd? (list 2 3 4 5)) + @result{} #t +@end lisp +@end defun + +@defun every? pred . collections +A generalization of the list-based @code{every} (@xref{Lists as +sequences}) to collections.@refill + +Example: +@lisp +(every? collection? '((1 2) #(1 2))) + @result{} #t +@end lisp +@end defun + +@defun empty? collection +Returns @code{#t} iff there are no elements in @var{collection}. + +@code{(empty? @var{collection}) @equiv{} (zero? (size @var{collection}))} +@end defun + +@defun size collection +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. +@code{(setter list-ref)} doesn't work properly for element 0 of a +list.@refill +@end defun + +Here is a sample collection: @code{simple-table} which is also a +@code{table}.@refill +@lisp +(define-predicate TABLE?) +(define-operation (LOOKUP table key failure-object)) +(define-operation (ASSOCIATE! table key value)) ;; returns key +(define-operation (REMOVE! table key)) ;; returns value + +(define (MAKE-SIMPLE-TABLE) + (let ( (table (list)) ) + (object + ;; table behaviors + ((TABLE? self) #t) + ((SIZE self) (size table)) + ((PRINT self port) (format port "#<SIMPLE-TABLE>")) + ((LOOKUP self key failure-object) + (cond + ((assq key table) => cdr) + (else failure-object) + )) + ((ASSOCIATE! self key value) + (cond + ((assq key table) + => (lambda (bucket) (set-cdr! bucket value) key)) + (else + (set! table (cons (cons key value) table)) + key) + )) + ((REMOVE! self key);; returns old value + (cond + ((null? table) (slib:error "TABLE:REMOVE! Key not found: " key)) + ((eq? key (caar table)) + (let ( (value (cdar table)) ) + (set! table (cdr table)) + value) + ) + (else + (let loop ( (last table) (this (cdr table)) ) + (cond + ((null? this) + (slib:error "TABLE:REMOVE! Key not found: " key)) + ((eq? key (caar this)) + (let ( (value (cdar this)) ) + (set-cdr! last (cdr this)) + value) + ) + (else + (loop (cdr last) (cdr this))) + ) ) ) + )) + ;; collection behaviors + ((COLLECTION? self) #t) + ((GEN-KEYS self) (collect:list-gen-elts (map car table))) + ((GEN-ELTS self) (collect:list-gen-elts (map cdr table))) + ((FOR-EACH-KEY self proc) + (for-each (lambda (bucket) (proc (car bucket))) table) + ) + ((FOR-EACH-ELT self proc) + (for-each (lambda (bucket) (proc (cdr bucket))) table) + ) + ) ) ) +@end lisp + + + + + +@node Dynamic Data Type, Hash Tables, Collections, Data Structures +@section Dynamic Data Type + +@code{(require 'dynamic)} + +@defun make-dynamic obj +Create and returns a new @dfn{dynamic} whose global value is @var{obj}. +@end defun + +@defun dynamic? obj +Returns true if and only if @var{obj} is a dynamic. No object +satisfying @code{dynamic?} satisfies any of the other standard type +predicates.@refill +@end defun + +@defun dynamic-ref dyn +Return the value of the given dynamic in the current dynamic +environment. +@end defun + +@deffn Procedure dynamic-set! dyn obj +Change the value of the given dynamic to @var{obj} in the current +dynamic environment. The returned value is unspecified.@refill +@end deffn + +@defun call-with-dynamic-binding dyn obj thunk +Invoke and return the value of the given thunk in a new, nested dynamic +environment in which the given dynamic has been bound to a new location +whose initial contents are the value @var{obj}. This dynamic +environment has precisely the same extent as the invocation of the thunk +and is thus captured by continuations created within that invocation and +re-established by those continuations when they are invoked.@refill +@end defun + +The @code{dynamic-bind} macro is not implemented. + + + + +@node Hash Tables, Hashing, Dynamic Data Type, Data Structures +@section Hash Tables + +@code{(require 'hash-table)} + +@defun predicate->hash pred +Returns a hash function (like @code{hashq}, @code{hashv}, or +@code{hash}) corresponding to the equality predicate @var{pred}. +@var{pred} should be @code{eq?}, @code{eqv?}, @code{equal?}, @code{=}, +@code{char=?}, @code{char-ci=?}, @code{string=?}, or +@code{string-ci=?}.@refill +@end defun + +A hash table is a vector of association lists. + +@defun make-hash-table k +Returns a vector of @var{k} empty (association) lists. +@end defun + +Hash table functions provide utilities for an associative database. +These functions take an equality predicate, @var{pred}, as an argument. +@var{pred} should be @code{eq?}, @code{eqv?}, @code{equal?}, @code{=}, +@code{char=?}, @code{char-ci=?}, @code{string=?}, or +@code{string-ci=?}.@refill + +@defun predicate->hash-asso pred +Returns a hash association function of 2 arguments, @var{key} and +@var{hashtab}, corresponding to @var{pred}. The returned function +returns a key-value pair whose key is @var{pred}-equal to its first +argument or @code{#f} if no key in @var{hashtab} is @var{pred}-equal to +the first argument.@refill +@end defun + +@defun hash-inquirer pred +Returns a procedure of 3 arguments, @code{hashtab} and @code{key}, which +returns the value associated with @code{key} in @code{hashtab} or +@code{#f} if key does not appear in @code{hashtab}.@refill +@end defun + +@defun hash-associator pred +Returns a procedure of 3 arguments, @var{hashtab}, @var{key}, and +@var{value}, which modifies @var{hashtab} so that @var{key} and +@var{value} associated. Any previous value associated with @var{key} +will be lost.@refill +@end defun + +@defun hash-remover pred +Returns a procedure of 2 arguments, @var{hashtab} and @var{key}, which +modifies @var{hashtab} so that the association whose key is @var{key} is +removed.@refill +@end defun + +@defun hash-map proc hash-table +Returns a new hash table formed by mapping @var{proc} over the +keys and values of @var{hash-table}. @var{proc} must be a function of 2 +arguments which returns the new value part. +@end defun + +@defun hash-for-each proc hash-table +Applies @var{proc} to each pair of keys and values of @var{hash-table}. +@var{proc} must be a function of 2 arguments. The returned value is +unspecified. +@end defun + + + + + +@node Hashing, Chapter Ordering, Hash Tables, Data Structures +@section Hashing + +@code{(require 'hash)} + +These hashing functions are for use in quickly classifying objects. +Hash tables use these functions. + +@defun hashq obj k +@defunx hashv obj k +@defunx hash obj k +Returns an exact non-negative integer less than @var{k}. For each +non-negative integer less than @var{k} there are arguments @var{obj} for +which the hashing functions applied to @var{obj} and @var{k} returns +that integer.@refill + +For @code{hashq}, @code{(eq? obj1 obj2)} implies @code{(= (hashq obj1 k) +(hashq obj2))}.@refill + +For @code{hashv}, @code{(eqv? obj1 obj2)} implies @code{(= (hashv obj1 k) +(hashv obj2))}.@refill + +For @code{hash}, @code{(equal? obj1 obj2)} implies @code{(= (hash obj1 k) +(hash obj2))}.@refill + +@code{hash}, @code{hashv}, and @code{hashq} return in time bounded by a +constant. Notice that items having the same @code{hash} implies the +items have the same @code{hashv} implies the items have the same +@code{hashq}.@refill +@end defun + + +@code{(require 'sierpinski)} + +@defun make-sierpinski-indexer max-coordinate +Returns a procedure (eg hash-function) of 2 numeric arguments which +preserves @emph{nearness} in its mapping from NxN to N. + +@var{max-coordinate} is the maximum coordinate (a positive integer) of a +population of points. The returned procedures is a function that takes +the x and y coordinates of a point, (non-negative integers) and returns +an integer corresponding to the relative position of that point along a +Sierpinski curve. (You can think of this as computing a (pseudo-) +inverse of the Sierpinski spacefilling curve.) + +Example use: Make an indexer (hash-function) for integer points lying in +square of integer grid points [0,99]x[0,99]: +@example +(define space-key (make-sierpinski-indexer 100)) +@end example +Now let's compute the index of some points: +@example +(space-key 24 78) @result{} 9206 +(space-key 23 80) @result{} 9172 +@end example + +Note that locations (24, 78) and (23, 80) are near in index and +therefore, because the Sierpinski spacefilling curve is continuous, we +know they must also be near in the plane. Nearness in the plane does +not, however, necessarily correspond to nearness in index, although it +@emph{tends} to be so. + +Example applications: +@table @asis + +@item +Sort points by Sierpinski index to get heuristic solution to +@emph{travelling salesman problem}. For details of performance, +see L. Platzman and J. Bartholdi, "Spacefilling curves and the +Euclidean travelling salesman problem", JACM 36(4):719--737 +(October 1989) and references therein. + +@item +Use Sierpinski index as key by which to store 2-dimensional data +in a 1-dimensional data structure (such as a table). Then +locations that are near each other in 2-d space will tend to +be near each other in 1-d data structure; and locations that +are near in 1-d data structure will be near in 2-d space. This +can significantly speed retrieval from secondary storage because +contiguous regions in the plane will tend to correspond to +contiguous regions in secondary storage. (This is a standard +technique for managing CAD/CAM or geographic data.) + +@end table +@end defun + + + +@code{(require 'soundex)} + +@defun soundex name +Computes the @emph{soundex} hash of @var{name}. Returns a string of an +initial letter and up to three digits between 0 and 6. Soundex +supposedly has the property that names that sound similar in normal +English pronunciation tend to map to the same key. + +Soundex was a classic algorithm used for manual filing of personal +records before the advent of computers. It performs adequately for +English names but has trouble with other nationalities. + +See Knuth, Vol. 3 @cite{Sorting and searching}, pp 391--2 + +To manage unusual inputs, @code{soundex} omits all non-alphabetic +characters. Consequently, in this implementation: + +@example +(soundex <string of blanks>) @result{} "" +(soundex "") @result{} "" +@end example + +Examples from Knuth: + +@example +(map soundex '("Euler" "Gauss" "Hilbert" "Knuth" + "Lloyd" "Lukasiewicz")) + @result{} ("E460" "G200" "H416" "K530" "L300" "L222") + +(map soundex '("Ellery" "Ghosh" "Heilbronn" "Kant" + "Ladd" "Lissajous")) + @result{} ("E460" "G200" "H416" "K530" "L300" "L222") +@end example + +Some cases in which the algorithm fails (Knuth): + +@example +(map soundex '("Rogers" "Rodgers")) @result{} ("R262" "R326") + +(map soundex '("Sinclair" "St. Clair")) @result{} ("S524" "S324") + +(map soundex '("Tchebysheff" "Chebyshev")) @result{} ("T212" "C121") +@end example +@end defun + +@node Chapter Ordering, Object, Hashing, Data Structures +@section Chapter Ordering + +@code{(require 'chapter-order)} + +The @samp{chap:} functions deal with strings which are ordered like +chapter numbers (or letters) in a book. Each section of the string +consists of consecutive numeric or consecutive aphabetic characters of +like case. + +@defun chap:string<? string1 string2 +Returns #t if the first non-matching run of alphabetic upper-case or the +first non-matching run of alphabetic lower-case or the first +non-matching run of numeric characters of @var{string1} is +@code{string<?} than the corresponding non-matching run of characters of +@var{string2}. + +@example +(chap:string<? "a.9" "a.10") @result{} #t +(chap:string<? "4c" "4aa") @result{} #t +(chap:string<? "Revised^@{3.99@}" "Revised^@{4@}") @result{} #t +@end example + +@defunx chap:string>? string1 string2 +@defunx chap:string<=? string1 string2 +@defunx chap:string>=? string1 string2 +Implement the corresponding chapter-order predicates. +@end defun + +@defun chap:next-string string +Returns the next string in the @emph{chapter order}. If @var{string} +has no alphabetic or numeric characters, +@code{(string-append @var{string} "0")} is returnd. The argument to +chap:next-string will always be @code{chap:string<?} than the result. + +@example +(chap:next-string "a.9") @result{} "a.10" +(chap:next-string "4c") @result{} "4d" +(chap:next-string "4z") @result{} "4aa" +(chap:next-string "Revised^@{4@}") @result{} "Revised^@{5@}" + +@end example +@end defun + +@node Object, Parameter lists, Chapter Ordering, Data Structures +@section Macroless Object System + +@code{(require 'object)} + +This is the Macroless Object System written by Wade Humeniuk +(whumeniu@@datap.ca). Conceptual Tributes: @ref{Yasos}, MacScheme's +%object, CLOS, Lack of R4RS macros. + +@subsection Concepts +@table @asis + +@item OBJECT +An object is an ordered association-list (by @code{eq?}) of methods +(procedures). Methods can be added (@code{make-method!}), deleted +(@code{unmake-method!}) and retrieved (@code{get-method}). Objects may +inherit methods from other objects. The object binds to the environment +it was created in, allowing closures to be used to hide private +procedures and data. + +@item GENERIC-METHOD +A generic-method associates (in terms of @code{eq?}) object's method. +This allows scheme function style to be used for objects. The calling +scheme for using a generic method is @code{(generic-method object param1 +param2 ...)}. + +@item METHOD +A method is a procedure that exists in the object. To use a method +get-method must be called to look-up the method. Generic methods +implement the get-method functionality. Methods may be added to an +object associated with any scheme obj in terms of eq? + +@item GENERIC-PREDICATE +A generic method that returns a boolean value for any scheme obj. + +@item PREDICATE +A object's method asscociated with a generic-predicate. Returns +@code{#t}. +@end table + +@subsection Procedures + +@defun make-object ancestor @dots{} +Returns an object. Current object implementation is a tagged vector. +@var{ancestor}s are optional and must be objects in terms of object?. +@var{ancestor}s methods are included in the object. Multiple +@var{ancestor}s might associate the same generic-method with a method. +In this case the method of the @var{ancestor} first appearing in the +list is the one returned by @code{get-method}. +@end defun + +@defun object? obj +Returns boolean value whether @var{obj} was created by make-object. +@end defun + +@defun make-generic-method exception-procedure +Returns a procedure which be associated with an object's methods. If +@var{exception-procedure} is specified then it is used to process +non-objects. +@end defun + +@defun make-generic-predicate +Returns a boolean procedure for any scheme object. +@end defun + +@defun make-method! object generic-method method +Associates @var{method} to the @var{generic-method} in the object. The +@var{method} overrides any previous association with the +@var{generic-method} within the object. Using @code{unmake-method!} +will restore the object's previous association with the +@var{generic-method}. @var{method} must be a procedure. +@end defun + +@defun make-predicate! object generic-preciate +Makes a predicate method associated with the @var{generic-predicate}. +@end defun + +@defun unmake-method! object generic-method +Removes an object's association with a @var{generic-method} . +@end defun + +@defun get-method object generic-method +Returns the object's method associated (if any) with the +@var{generic-method}. If no associated method exists an error is +flagged. +@end defun + +@subsection Examples + +@example +(require 'object) + +(define instantiate (make-generic-method)) + +(define (make-instance-object . ancestors) + (define self (apply make-object + (map (lambda (obj) (instantiate obj)) ancestors))) + (make-method! self instantiate (lambda (self) self)) + self) + +(define who (make-generic-method)) +(define imigrate! (make-generic-method)) +(define emigrate! (make-generic-method)) +(define describe (make-generic-method)) +(define name (make-generic-method)) +(define address (make-generic-method)) +(define members (make-generic-method)) + +(define society + (let () + (define self (make-instance-object)) + (define population '()) + (make-method! self imigrate! + (lambda (new-person) + (if (not (eq? new-person self)) + (set! population (cons new-person population))))) + (make-method! self emigrate! + (lambda (person) + (if (not (eq? person self)) + (set! population + (comlist:remove-if (lambda (member) + (eq? member person)) + population))))) + (make-method! self describe + (lambda (self) + (map (lambda (person) (describe person)) population))) + (make-method! self who + (lambda (self) (map (lambda (person) (name person)) + population))) + (make-method! self members (lambda (self) population)) + self)) + +(define (make-person %name %address) + (define self (make-instance-object society)) + (make-method! self name (lambda (self) %name)) + (make-method! self address (lambda (self) %address)) + (make-method! self who (lambda (self) (name self))) + (make-method! self instantiate + (lambda (self) + (make-person (string-append (name self) "-son-of") + %address))) + (make-method! self describe + (lambda (self) (list (name self) (address self)))) + (imigrate! self) + self) +@end example + +@subsubsection Inverter Documentation +Inheritance: +@lisp + <inverter>::(<number> <description>) +@end lisp +Generic-methods +@lisp + <inverter>::value @result{} <number>::value + <inverter>::set-value! @result{} <number>::set-value! + <inverter>::describe @result{} <description>::describe + <inverter>::help + <inverter>::invert + <inverter>::inverter? +@end lisp + +@subsubsection Number Documention +Inheritance +@lisp + <number>::() +@end lisp +Slots +@lisp + <number>::<x> +@end lisp +Generic Methods +@lisp + <number>::value + <number>::set-value! +@end lisp + +@subsubsection Inverter code +@example +(require 'object) + +(define value (make-generic-method (lambda (val) val))) +(define set-value! (make-generic-method)) +(define invert (make-generic-method + (lambda (val) + (if (number? val) + (/ 1 val) + (error "Method not supported:" val))))) +(define noop (make-generic-method)) +(define inverter? (make-generic-predicate)) +(define describe (make-generic-method)) +(define help (make-generic-method)) + +(define (make-number x) + (define self (make-object)) + (make-method! self value (lambda (this) x)) + (make-method! self set-value! + (lambda (this new-value) (set! x new-value))) + self) + +(define (make-description str) + (define self (make-object)) + (make-method! self describe (lambda (this) str)) + (make-method! self help (lambda (this) "Help not available")) + self) + +(define (make-inverter) + (define self (make-object + (make-number 1) + (make-description "A number which can be inverted"))) + (define <value> (get-method self value)) + (make-method! self invert (lambda (self) (/ 1 (<value> self)))) + (make-predicate! self inverter?) + (unmake-method! self help) + (make-method! self help + (lambda (self) + (display "Inverter Methods:") (newline) + (display " (value inverter) ==> n") (newline))) + self) + +;;;; Try it out + +(define invert! (make-generic-method)) + +(define x (make-inverter)) + +(make-method! x invert! (lambda () (set-value! x (/ 1 (value x))))) + +(value x) @result{} 1 +(set-value! x 33) @result{} undefined +(invert! x) @result{} undefined +(value x) @result{} 1/33 + +(unmake-method! x invert!) @result{} undefined + +(invert! x) @error{} ERROR: Method not supported: x +@end example + +@node Parameter lists, Priority Queues, Object, Data Structures +@section Parameter lists + +@code{(require 'parameters)} + +@noindent +Arguments to procedures in scheme are distinguished from each other by +their position in the procedure call. This can be confusing when a +procedure takes many arguments, many of which are not often used. + +@noindent +A @dfn{parameter-list} is a way of passing named information to a +procedure. Procedures are also defined to set unused parameters to +default values, check parameters, and combine parameter lists. + +@noindent +A @var{parameter} has the form @code{(@r{parameter-name} @r{value1} +@dots{})}. This format allows for more than one value per +parameter-name. + +@noindent +A @var{parameter-list} is a list of @var{parameter}s, each with a +different @var{parameter-name}. + +@deffn Function make-parameter-list parameter-names +Returns an empty parameter-list with slots for @var{parameter-names}. +@end deffn + +@deffn Function parameter-list-ref parameter-list parameter-name +@var{parameter-name} must name a valid slot of @var{parameter-list}. +@code{parameter-list-ref} returns the value of parameter +@var{parameter-name} of @var{parameter-list}. +@end deffn + +@deffn Procedure adjoin-parameters! parameter-list parameter1 @dots{} +Returns @var{parameter-list} with @var{parameter1} @dots{} merged in. +@end deffn + +@deffn Procedure parameter-list-expand expanders parameter-list +@var{expanders} is a list of procedures whose order matches the order of +the @var{parameter-name}s in the call to @code{make-parameter-list} +which created @var{parameter-list}. For each non-false element of +@var{expanders} that procedure is mapped over the corresponding +parameter value and the returned parameter lists are merged into +@var{parameter-list}. + +This process is repeated until @var{parameter-list} stops growing. The +value returned from @code{parameter-list-expand} is unspecified. +@end deffn + +@deffn Function fill-empty-parameters defaults parameter-list +@var{defaults} is a list of lists whose order matches the order of the +@var{parameter-name}s in the call to @code{make-parameter-list} which +created @var{parameter-list}. @code{fill-empty-parameters} returns a +new parameter-list with each empty parameter filled with the +corresponding @var{default}. +@end deffn + +@deffn Function check-parameters checks parameter-list +@var{checks} is a list of procedures whose order matches the order of +the @var{parameter-name}s in the call to @code{make-parameter-list} +which created @var{parameter-list}. + +@code{check-parameters} returns @var{parameter-list} if each @var{check} +of the corresponding @var{parameter-list} returns non-false. If some +@var{check} returns @code{#f} an error is signaled. +@end deffn + +@noindent +In the following procedures @var{arities} is a list of symbols. The +elements of @code{arities} can be: + +@table @code +@item single +Requires a single parameter. +@item optional +A single parameter or no parameter is acceptable. +@item boolean +A single boolean parameter or zero parameters is acceptable. +@item nary +Any number of parameters are acceptable. +@item nary1 +One or more of parameters are acceptable. +@end table + +@deffn Function parameter-list->arglist positions arities types parameter-list +Returns @var{parameter-list} converted to an argument list. Parameters +of @var{arity} type @code{single} and @code{boolean} are converted to +the single value associated with them. The other @var{arity} types are +converted to lists of the value(s) of type @var{types}. + +@var{positions} is a list of positive integers whose order matches the +order of the @var{parameter-name}s in the call to +@code{make-parameter-list} which created @var{parameter-list}. The +integers specify in which argument position the corresponding parameter +should appear. +@end deffn + +@deffn Function getopt->parameter-list argc argv optnames arities types aliases +Returns @var{argv} converted to a parameter-list. @var{optnames} are +the parameter-names. @var{aliases} is a list of lists of strings and +elements of @var{optnames}. Each of these strings which have length of +1 will be treated as a single @key{-} option by @code{getopt}. Longer +strings will be treated as long-named options (@pxref{Getopt, getopt--}). +@end deffn + +@deffn Function getopt->arglist argc argv optnames positions arities types defaults checks aliases +Like @code{getopt->parameter-list}, but converts @var{argv} to an +argument-list as specified by @var{optnames}, @var{positions}, +@var{arities}, @var{types}, @var{defaults}, @var{checks}, and +@var{aliases}. +@end deffn + +These @code{getopt} functions can be used with SLIB relational +databases. For an example, @xref{Database Utilities, +make-command-server}. + +@node Priority Queues, Queues, Parameter lists, Data Structures +@section Priority Queues + +@code{(require 'priority-queue)} + +@defun make-heap pred<? +Returns a binary heap suitable which can be used for priority queue +operations. +@end defun + +@defun heap-length heap +Returns the number of elements in @var{heap}.@refill +@end defun + +@deffn Procedure heap-insert! heap item +Inserts @var{item} into @var{heap}. @var{item} can be inserted multiple +times. The value returned is unspecified.@refill +@end deffn + +@defun heap-extract-max! heap +Returns the item which is larger than all others according to the +@var{pred<?} argument to @code{make-heap}. If there are no items in +@var{heap}, an error is signaled.@refill +@end defun + +The algorithm for priority queues was taken from @cite{Introduction to +Algorithms} by T. Cormen, C. Leiserson, R. Rivest. 1989 MIT Press. + + + +@node Queues, Records, Priority Queues, Data Structures +@section Queues + +@code{(require 'queue)} + +A @dfn{queue} is a list where elements can be added to both the front +and rear, and removed from the front (i.e., they are what are often +called @dfn{dequeues}). A queue may also be used like a stack.@refill + +@defun make-queue +Returns a new, empty queue. +@end defun + +@defun queue? obj +Returns @code{#t} if @var{obj} is a queue. +@end defun + +@defun queue-empty? q +Returns @code{#t} if the queue @var{q} is empty. +@end defun + +@deffn Procedure queue-push! q datum +Adds @var{datum} to the front of queue @var{q}. +@end deffn + +@deffn Procedure enquque! q datum +Adds @var{datum} to the rear of queue @var{q}. +@end deffn + +All of the following functions raise an error if the queue @var{q} is +empty.@refill + +@defun queue-front q +Returns the datum at the front of the queue @var{q}. +@end defun + +@defun queue-rear q +Returns the datum at the rear of the queue @var{q}. +@end defun + +@deffn Prcoedure queue-pop! q +@deffnx Procedure dequeue! q +Both of these procedures remove and return the datum at the front of the +queue. @code{queue-pop!} is used to suggest that the queue is being +used like a stack.@refill +@end deffn + + + + + +@node Records, Base Table, Queues, Data Structures +@section Records + +@code{(require 'record)} + +The Record package provides a facility for user to define their own +record data types. + +@defun make-record-type type-name field-names +Returns a @dfn{record-type descriptor}, a value representing a new data +type disjoint from all others. The @var{type-name} argument must be a +string, but is only used for debugging purposes (such as the printed +representation of a record of the new type). The @var{field-names} +argument is a list of symbols naming the @dfn{fields} of a record of the +new type. It is an error if the list contains any duplicates. It is +unspecified how record-type descriptors are represented.@refill +@end defun + +@c @defun make-record-sub-type type-name field-names rtd +@c Returns a @dfn{record-type descriptor}, a value representing a new data +@c type, disjoint from all others. The @var{type-name} argument must be a +@c string. The @var{field-names} argument is a list of symbols naming the +@c additional @dfn{fields} to be appended to @var{field-names} of +@c @var{rtd}. It is an error if the combinded list contains any +@c duplicates.@refill +@c +@c Record-modifiers and record-accessors for @var{rtd} work for the new +@c record-sub-type as well. But record-modifiers and record-accessors for +@c the new record-sub-type will not neccessarily work for @var{rtd}.@refill +@c @end defun + +@defun record-constructor rtd [field-names] +Returns a procedure for constructing new members of the type represented +by @var{rtd}. The returned procedure accepts exactly as many arguments +as there are symbols in the given list, @var{field-names}; these are +used, in order, as the initial values of those fields in a new record, +which is returned by the constructor procedure. The values of any +fields not named in that list are unspecified. The @var{field-names} +argument defaults to the list of field names in the call to +@code{make-record-type} that created the type represented by @var{rtd}; +if the @var{field-names} argument is provided, it is an error if it +contains any duplicates or any symbols not in the default list.@refill +@end defun + +@defun record-predicate rtd +Returns a procedure for testing membership in the type represented by +@var{rtd}. The returned procedure accepts exactly one argument and +returns a true value if the argument is a member of the indicated record +type; it returns a false value otherwise.@refill +@end defun + +@c @defun record-sub-predicate rtd +@c Returns a procedure for testing membership in the type represented by +@c @var{rtd} or its parents. The returned procedure accepts exactly one +@c argument and returns a true value if the argument is a member of the +@c indicated record type or its parents; it returns a false value +@c otherwise.@refill +@c @end defun + +@defun record-accessor rtd field-name +Returns a procedure for reading the value of a particular field of a +member of the type represented by @var{rtd}. The returned procedure +accepts exactly one argument which must be a record of the appropriate +type; it returns the current value of the field named by the symbol +@var{field-name} in that record. The symbol @var{field-name} must be a +member of the list of field-names in the call to @code{make-record-type} +that created the type represented by @var{rtd}.@refill +@end defun + + +@defun record-modifier rtd field-name +Returns a procedure for writing the value of a particular field of a +member of the type represented by @var{rtd}. The returned procedure +accepts exactly two arguments: first, a record of the appropriate type, +and second, an arbitrary Scheme value; it modifies the field named by +the symbol @var{field-name} in that record to contain the given value. +The returned value of the modifier procedure is unspecified. The symbol +@var{field-name} must be a member of the list of field-names in the call +to @code{make-record-type} that created the type represented by +@var{rtd}.@refill +@end defun + +@defun record? obj +Returns a true value if @var{obj} is a record of any type and a false +value otherwise. Note that @code{record?} may be true of any Scheme +value; of course, if it returns true for some particular value, then +@code{record-type-descriptor} is applicable to that value and returns an +appropriate descriptor.@refill +@end defun + +@defun record-type-descriptor record +Returns a record-type descriptor representing the type of the given +record. That is, for example, if the returned descriptor were passed to +@code{record-predicate}, the resulting predicate would return a true +value when passed the given record. Note that it is not necessarily the +case that the returned descriptor is the one that was passed to +@code{record-constructor} in the call that created the constructor +procedure that created the given record.@refill +@end defun + +@defun record-type-name rtd +Returns the type-name associated with the type represented by rtd. The +returned value is @code{eqv?} to the @var{type-name} argument given in +the call to @code{make-record-type} that created the type represented by +@var{rtd}.@refill +@end defun + +@defun record-type-field-names rtd +Returns a list of the symbols naming the fields in members of the type +represented by @var{rtd}. The returned value is @code{equal?} to the +field-names argument given in the call to @code{make-record-type} that +created the type represented by @var{rtd}.@refill +@end defun + + + +@node Base Table, Relational Database, Records, Data Structures +@section Base Table + +A base table implementation using Scheme association lists is available +as the value of the identifier @code{alist-table} after doing: + +@example +(require 'alist-table) +@end example + + +Association list base tables are suitable for small databases and +support all Scheme types when temporary and readable/writeable Scheme +types when saved. I hope support for other base table implementations +will be added in the future. + +This rest of this section documents the interface for a base table +implementation from which the @ref{Relational Database} package +constructs a Relational system. It will be of interest primarily to +those wishing to port or write new base-table implementations. + +All of these functions are accessed through a single procedure by +calling that procedure with the symbol name of the operation. A +procedure will be returned if that operation is supported and @code{#f} +otherwise. For example: + +@example +@group +(require 'alist-table) +(define open-base (alist-table 'make-base)) +make-base @result{} *a procedure* +(define foo (alist-table 'foo)) +foo @result{} #f +@end group +@end example + +@defun make-base filename key-dimension column-types +Returns a new, open, low-level database (collection of tables) +associated with @var{filename}. This returned database has an empty +table associated with @var{catalog-id}. The positive integer +@var{key-dimension} is the number of keys composed to make a +@var{primary-key} for the catalog table. The list of symbols +@var{column-types} describes the types of each column for that table. +If the database cannot be created as specified, @code{#f} is returned. + +Calling the @code{close-base} method on this database and possibly other +operations will cause @var{filename} to be written to. If +@var{filename} is @code{#f} a temporary, non-disk based database will be +created if such can be supported by the base table implelentation. +@end defun + +@defun open-base filename mutable +Returns an open low-level database associated with @var{filename}. If +@var{mutable?} is @code{#t}, this database will have methods capable of +effecting change to the database. If @var{mutable?} is @code{#f}, only +methods for inquiring the database will be available. If the database +cannot be opened as specified @code{#f} is returned. + +Calling the @code{close-base} (and possibly other) method on a +@var{mutable?} database will cause @var{filename} to be written to. +@end defun + +@defun write-base lldb filename +Causes the low-level database @var{lldb} to be written to +@var{filename}. If the write is successful, also causes @var{lldb} to +henceforth be associated with @var{filename}. Calling the +@code{close-database} (and possibly other) method on @var{lldb} may +cause @var{filename} to be written to. If @var{filename} is @code{#f} +this database will be changed to a temporary, non-disk based database if +such can be supported by the underlying base table implelentation. If +the operations completed successfully, @code{#t} is returned. +Otherwise, @code{#f} is returned. +@end defun + +@defun sync-base lldb +Causes the file associated with the low-level database @var{lldb} to be +updated to reflect its current state. If the associated filename is +@code{#f}, no action is taken and @code{#f} is returned. If this +operation completes successfully, @code{#t} is returned. Otherwise, +@code{#f} is returned. +@end defun + +@defun close-base lldb +Causes the low-level database @var{lldb} to be written to its associated +file (if any). If the write is successful, subsequent operations to +@var{lldb} will signal an error. If the operations complete +successfully, @code{#t} is returned. Otherwise, @code{#f} is returned. +@end defun + +@defun make-table lldb key-dimension column-types +Returns the @var{base-id} for a new base table, otherwise returns +@code{#f}. The base table can then be opened using @code{(open-table +@var{lldb} @var{base-id})}. The positive integer @var{key-dimension} is +the number of keys composed to make a @var{primary-key} for this table. +The list of symbols @var{column-types} describes the types of each +column. +@end defun + +@defvr Constant catalog-id +A constant @var{base-id} suitable for passing as a parameter to +@code{open-table}. @var{catalog-id} will be used as the base table for +the system catalog. +@end defvr + +@defun open-table lldb base-id key-dimension column-types +Returns a @var{handle} for an existing base table in the low-level +database @var{lldb} if that table exists and can be opened in the mode +indicated by @var{mutable?}, otherwise returns @code{#f}. + +As with @code{make-table}, the positive integer @var{key-dimension} is +the number of keys composed to make a @var{primary-key} for this table. +The list of symbols @var{column-types} describes the types of each +column. +@end defun + +@defun kill-table lldb base-id key-dimension column-types +Returns @code{#t} if the base table associated with @var{base-id} was +removed from the low level database @var{lldb}, and @code{#f} otherwise. +@end defun + +@defun make-keyifier-1 type +Returns a procedure which accepts a single argument which must be of +type @var{type}. This returned procedure returns an object suitable for +being a @var{key} argument in the functions whose descriptions follow. + +Any 2 arguments of the supported type passed to the returned function +which are not @code{equal?} must result in returned values which are not +@code{equal?}. +@end defun + +@defun make-list-keyifier key-dimension types +The list of symbols @var{types} must have at least @var{key-dimension} +elements. Returns a procedure which accepts a list of length +@var{key-dimension} and whose types must corresopond to the types named +by @var{types}. This returned procedure combines the elements of its +list argument into an object suitable for being a @var{key} argument in +the functions whose descriptions follow. + +Any 2 lists of supported types (which must at least include symbols and +non-negative integers) passed to the returned function which are not +@code{equal?} must result in returned values which are not +@code{equal?}. +@end defun + +@defun make-key-extractor key-dimension types column-number +Returns a procedure which accepts objects produced by application of the +result of @code{(make-list-keyifier @var{key-dimension} @var{types})}. +This procedure returns a @var{key} which is @code{equal?} to the +@var{column-number}th element of the list which was passed to create +@var{combined-key}. The list @var{types} must have at least +@var{key-dimension} elements. +@end defun + +@defun make-key->list key-dimension types +Returns a procedure which accepts objects produced by application of the +result of @code{(make-list-keyifier @var{key-dimension} @var{types})}. +This procedure returns a list of @var{key}s which are elementwise +@code{equal?} to the list which was passed to create @var{combined-key}. +@end defun + +@noindent +In the following functions, the @var{key} argument can always be assumed +to be the value returned by a call to a @emph{keyify} routine. + +@defun for-each-key handle procedure +Calls @var{procedure} once with each @var{key} in the table opened in +@var{handle} in an unspecified order. An unspecified value is returned. +@end defun + +@defun map-key handle procedure +Returns a list of the values returned by calling @var{procedure} once +with each @var{key} in the table opened in @var{handle} in an +unspecified order. +@end defun + +@defun ordered-for-each-key handle procedure +Calls @var{procedure} once with each @var{key} in the table opened in +@var{handle} in the natural order for the types of the primary key +fields of that table. An unspecified value is returned. +@end defun + +@defun present? handle key +Returns a non-@code{#f} value if there is a row associated with +@var{key} in the table opened in @var{handle} and @code{#f} otherwise. +@end defun + +@defun delete handle key +Removes the row associated with @var{key} from the table opened in +@var{handle}. An unspecified value is returned. +@end defun + +@defun make-getter key-dimension types +Returns a procedure which takes arguments @var{handle} and @var{key}. +This procedure returns a list of the non-primary values of the relation +(in the base table opened in @var{handle}) whose primary key is +@var{key} if it exists, and @code{#f} otherwise. +@end defun + +@defun make-putter key-dimension types +Returns a procedure which takes arguments @var{handle} and @var{key} and +@var{value-list}. This procedure associates the primary key @var{key} +with the values in @var{value-list} (in the base table opened in +@var{handle}) and returns an unspecified value. +@end defun + +@defun supported-type? symbol +Returns @code{#t} if @var{symbol} names a type allowed as a column value +by the implementation, and @code{#f} otherwise. At a minimum, an +implementation must support the types @code{integer}, @code{symbol}, +@code{string}, @code{boolean}, and @code{base-id}. +@end defun + +@defun supported-key-type? symbol +Returns @code{#t} if @var{symbol} names a type allowed as a key value by +the implementation, and @code{#f} otherwise. At a minimum, an +implementation must support the types @code{integer}, and @code{symbol}. +@end defun + +@table @code +@item integer +Scheme exact integer. +@item symbol +Scheme symbol. +@item boolean +@code{#t} or @code{#f}. +@item base-id +Objects suitable for passing as the @var{base-id} parameter to +@code{open-table}. The value of @var{catalog-id} must be an acceptable +@code{base-id}. +@end table + +@node Relational Database, Weight-Balanced Trees, Base Table, Data Structures +@section Relational Database + +@code{(require 'relational-database)} + +This package implements a database system inspired by the Relational +Model (@cite{E. F. Codd, A Relational Model of Data for Large Shared +Data Banks}). An SLIB relational database implementation can be created +from any @ref{Base Table} implementation. + +@menu +* Motivations:: Database Manifesto +* Creating and Opening Relational Databases:: +* Relational Database Operations:: +* Table Operations:: +* Catalog Representation:: +* Unresolved Issues:: +* Database Utilities:: 'database-utilities +@end menu + +@node Motivations, Creating and Opening Relational Databases, Relational Database, Relational Database +@subsection Motivations + +Most nontrivial programs contain databases: Makefiles, configure +scripts, file backup, calendars, editors, source revision control, CAD +systems, display managers, menu GUIs, games, parsers, debuggers, +profilers, and even error reporting are all rife with databases. Coding +databases is such a common activity in programming that many may not be +aware of how often they do it. + +A database often starts as a dispatch in a program. The author, perhaps +because of the need to make the dispatch configurable, the need for +correlating dispatch in other routines, or because of changes or growth, +devises a data structure to contain the information, a routine for +interpreting that data structure, and perhaps routines for augmenting +and modifying the stored data. The dispatch must be converted into this +form and tested. + +The programmer may need to devise an interactive program for enabling +easy examination and modification of the information contained in this +database. Often, in an attempt to foster modularity and avoid delays in +release, intermediate file formats for the database information are +devised. It often turns out that users prefer modifying these +intermediate files with a text editor to using the interactive program +in order to do operations (such as global changes) not forseen by the +program's author. + +In order to address this need, the concientous software engineer may +even provide a scripting language to allow users to make repetitive +database changes. Users will grumble that they need to read a large +manual and learn yet another programming language (even if it +@emph{almost} has language "xyz" syntax) in order to do simple +configuration. + +All of these facilities need to be designed, coded, debugged, +documented, and supported; often causing what was very simple in concept +to become a major developement project. + +This view of databases just outlined is somewhat the reverse of the view +of the originators of the @dfn{Relational Model} of database +abstraction. The relational model was devised to unify and allow +interoperation of large multi-user databases running on diverse +platforms. A fairly general purpose "Comprehensive Language" for +database manipulations is mandated (but not specified) as part of the +relational model for databases. + +One aspect of the Relational Model of some importance is that the +"Comprehensive Language" must be expressible in some form which can be +stored in the database. This frees the programmer from having to make +programs data-driven in order to use a database. + +This package includes as one of its basic supported types Scheme +@dfn{expression}s. This type allows expressions as defined by the +Scheme standards to be stored in the database. Using @code{slib:eval} +retrieved expressions can be evaluated (in the top-level environment). +Scheme's @code{lambda} facilitates closure of environments, modularity, +etc. so that procedures (which could not be stored directly most +databases) can still be effectively retrieved. Since @code{slib:eval} +evaluates expressions in the top-level environment, built-in and user +defined procedures can be easily accessed by name. + +This package's purpose is to standardize (through a common interface) +database creation and usage in Scheme programs. The relational model's +provision for inclusion of language expressions as data as well as the +description (in tables, of course) of all of its tables assures that +relational databases are powerful enough to assume the roles currently +played by thousands of ad-hoc routines and data formats. + +@noindent +Such standardization to a relational-like model brings many benefits: + +@itemize @bullet +@item +Tables, fields, domains, and types can be dealt with by name in +programs. +@item +The underlying database implementation can be changed (for +performance or other reasons) by changing a single line of code. +@item +The formats of tables can be easily extended or changed without +altering code. +@item +Consistency checks are specified as part of the table descriptions. +Changes in checks need only occur in one place. +@item +All the configuration information which the developer wishes to group +together is easily grouped, without needing to change programs aware of +only some of these tables. +@item +Generalized report generators, interactive entry programs, and other +database utilities can be part of a shared library. The burden of +adding configurability to a program is greatly reduced. +@item +Scheme is the "comprehensive language" for these databases. Scripting +for configuration no longer needs to be in a separate language with +additional documentation. +@item +Scheme's latent types mesh well with the strict typing and logical +requirements of the relational model. +@item +Portable formats allow easy interchange of data. The included table +descriptions help prevent misinterpretation of format. +@end itemize + +@node Creating and Opening Relational Databases, Relational Database Operations, Motivations, Relational Database +@subsection Creating and Opening Relational Databases + +@defun make-relational-system base-table-implementation + +Returns a procedure implementing a relational database using the +@var{base-table-implementation}. + +All of the operations of a base table implementation are accessed +through a procedure defined by @code{require}ing that implementation. +Similarly, all of the operations of the relational database +implementation are accessed through the procedure returned by +@code{make-relational-system}. For instance, a new relational database +could be created from the procedure returned by +@code{make-relational-system} by: + +@example +(require 'alist-table) +(define relational-alist-system + (make-relational-system alist-table)) +(define create-alist-database + (relational-alist-system 'create-database)) +(define my-database + (create-alist-database "mydata.db")) +@end example +@end defun + +@noindent +What follows are the descriptions of the methods available from +relational system returned by a call to @code{make-relational-system}. + +@defun create-database filename + +Returns an open, nearly empty relational database associated with +@var{filename}. The only tables defined are the system catalog and +domain table. Calling the @code{close-database} method on this database +and possibly other operations will cause @var{filename} to be written +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} +@end defun + +@defun open-database filename mutable? + +Returns an open relational database associated with @var{filename}. If +@var{mutable?} is @code{#t}, this database will have methods capable of +effecting change to the database. If @var{mutable?} is @code{#f}, only +methods for inquiring the database will be available. Calling the +@code{close-database} (and possibly other) method on a @var{mutable?} +database will cause @var{filename} to be written to. If the database +cannot be opened as specified @code{#f} is returned. +@end defun + +@node Relational Database Operations, Table Operations, Creating and Opening Relational Databases, Relational Database +@subsection Relational Database Operations + +@noindent +These are the descriptions of the methods available from an open +relational database. A method is retrieved from a database by calling +the database with the symbol name of the operation. For example: + +@example +(define my-database + (create-alist-database "mydata.db")) +(define telephone-table-desc + ((my-database 'create-table) 'telephone-table-desc)) +@end example + +@defun close-database +Causes the relational database to be written to its associated file (if +any). If the write is successful, subsequent operations to this +database will signal an error. If the operations completed +successfully, @code{#t} is returned. Otherwise, @code{#f} is returned. +@end defun + +@defun write-database filename +Causes the relational database to be written to @var{filename}. If the +write is successful, also causes the database to henceforth be +associated with @var{filename}. Calling the @code{close-database} (and +possibly other) method on this database will cause @var{filename} to be +written to. If @var{filename} is @code{#f} this database will be +changed to a temporary, non-disk based database if such can be supported +by the underlying base table implelentation. If the operations +completed successfully, @code{#t} is returned. Otherwise, @code{#f} is +returned. +@end defun + +@defun table-exists? table-name +Returns @code{#t} if @var{table-name} exists in the system catalog, +otherwise returns @code{#f}. +@end defun + +@defun open-table table-name mutable? +Returns a @dfn{methods} procedure for an existing relational table in +this database if it exists and can be opened in the mode indicated by +@var{mutable?}, otherwise returns @code{#f}. +@end defun + +@noindent +These methods will be present only in databases which are +@var{mutable?}. + +@defun delete-table table-name +Removes and returns the @var{table-name} row from the system catalog if +the table or view associated with @var{table-name} gets removed from the +database, and @code{#f} otherwise. +@end defun + +@defun create-table table-desc-name +Returns a methods procedure for a new (open) relational table for +describing the columns of a new base table in this database, otherwise +returns @code{#f}. For the fields and layout of descriptor tables, +@xref{Catalog Representation}. + +@defunx create-table table-name table-desc-name +Returns a methods procedure for a new (open) relational table with +columns as described by @var{table-desc-name}, otherwise returns +@code{#f}. +@end defun + +@defun create-view ?? +@defunx project-table ?? +@defunx restrict-table ?? +@defunx cart-prod-tables ?? +Not yet implemented. +@end defun + +@node Table Operations, Catalog Representation, Relational Database Operations, Relational Database +@subsection Table Operations + +@noindent +These are the descriptions of the methods available from an open +relational table. A method is retrieved from a table by calling +the table with the symbol name of the operation. For example: + +@example +@group +(define telephone-table-desc + ((my-database 'create-table) 'telephone-table-desc)) +(require 'common-list-functions) +(define ndrp (telephone-table-desc 'row:insert)) +(ndrp '(1 #t name #f string)) +(ndrp '(2 #f telephone + (lambda (d) + (and (string? d) (> (string-length d) 2) + (every + (lambda (c) + (memv c '(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9 + #\+ #\( #\ #\) #\-))) + (string->list d)))) + string)) +@end group +@end example + +@noindent +Operations on a single column of a table are retrieved by giving the +column name as the second argument to the methods procedure. For +example: + +@example +(define column-ids ((telephone-table-desc 'get* 'column-number))) +@end example + +@noindent +Some operations described below require primary key arguments. Primary +keys arguments are denoted @var{key1} @var{key2} @dots{}. It is an +error to call an operation for a table which takes primary key arguments +with the wrong number of primary keys for that table. + +@noindent +The term @dfn{row} used below refers to a Scheme list of values (one for +each column) in the order specified in the descriptor (table) for this +table. Missing values appear as @code{#f}. Primary keys may not +be missing. + +@defun get key1 key2 @dots{} +Returns the value for the specified column of the row associated with +primary keys @var{key1}, @var{key2} @dots{} if it exists, or @code{#f} +otherwise. + +@defunx get* +Returns a list of the values for the specified column for all rows in +this table. + +@defunx row:retrieve key1 key2 @dots{} +Returns the row associated with primary keys @var{key1}, @var{key2} +@dots{} if it exists, or @code{#f} otherwise. + +@defunx row:retrieve* +Returns a list of all rows in this table. +@end defun + +@defun row:remove key1 key2 @dots{} +Removes and returns the row associated with primary keys @var{key1}, +@var{key2} @dots{} if it exists, or @code{#f} otherwise. + +@defunx row:remove* +Removes and returns a list of all rows in this table. +@end defun + +@defun row:delete key1 key2 @dots{} +Deletes the row associated with primary keys @var{key1}, @var{key2} +@dots{} if it exists. The value returned is unspecified. + +@defunx row:delete* +Deletes all rows in this table. The value returned is unspecified. The +descriptor table and catalog entry for this table are not affected. +@end defun + +@defun row:update row +Adds the row, @var{row}, to this table. If a row for the primary key(s) +specified by @var{row} already exists in this table, it will be +overwritten. The value returned is unspecified. + +@defunx row:update* rows +Adds each row in the list @var{rows}, to this table. If a row for the +primary key specified by an element of @var{rows} already exists in this +table, it will be overwritten. The value returned is unspecified. +@end defun + +@defun row:insert row +Adds the row @var{row} to this table. If a row for the primary key(s) +specified by @var{row} already exists in this table an error is +signaled. The value returned is unspecified. + +@defunx row:insert* rows +Adds each row in the list @var{rows}, to this table. If a row for the +primary key specified by an element of @var{rows} already exists in this +table, an error is signaled. The value returned is unspecified. +@end defun + +@defun for-each-row proc +Calls @var{proc} with each @var{row} in this table in the natural +ordering for the primary key types. @emph{Real} relational programmers +would use some least-upper-bound join for every row to get them in +order; But we don't have joins yet. +@end defun + +@defun close-table +Subsequent operations to this table will signal an error. +@end defun + +@defvr Constant column-names +@defvrx Constant column-foreigns +@defvrx Constant column-domains +@defvrx Constant column-types +Return a list of the column names, foreign-key table names, domain +names, or type names respectively for this table. These 4 methods are +different from the others in that the list is returned, rather than a +procedure to obtain the list. + +@defvrx Constant primary-limit +Returns the number of primary keys fields in the relations in this +table. +@end defvr + +@node Catalog Representation, Unresolved Issues, Table Operations, Relational Database +@subsection Catalog Representation + +@noindent +Each database (in an implementation) has a @dfn{system catalog} which +describes all the user accessible tables in that database (including +itself). + +@noindent +The system catalog base table has the following fields. @code{PRI} +indicates a primary key for that table. + +@example +@group +PRI table-name + column-limit the highest column number + coltab-name descriptor table name + bastab-id data base table identifier + user-integrity-rule + view-procedure A scheme thunk which, when called, + produces a handle for the view. coltab + and bastab are specified if and only if + view-procedure is not. +@end group +@end example + +@noindent +Descriptors for base tables (not views) are tables (pointed to by +system catalog). Descriptor (base) tables have the fields: + +@example +@group +PRI column-number sequential integers from 1 + primary-key? boolean TRUE for primary key components + column-name + column-integrity-rule + domain-name +@end group +@end example + +@noindent +A @dfn{primary key} is any column marked as @code{primary-key?} in the +corresponding descriptor table. All the @code{primary-key?} columns +must have lower column numbers than any non-@code{primary-key?} columns. +Every table must have at least one primary key. Primary keys must be +sufficient to distinguish all rows from each other in the table. All of +the system defined tables have a single primary key. + +@noindent +This package currently supports tables having from 1 to 4 primary keys +if there are non-primary columns, and any (natural) number if @emph{all} +columns are primary keys. If you need more than 4 primary keys, I would +like to hear what you are doing! + +@noindent +A @dfn{domain} is a category describing the allowable values to occur in +a column. It is described by a (base) table with the fields: + +@example +@group +PRI domain-name + foreign-table + domain-integrity-rule + type-id + type-param +@end group +@end example + +@noindent +The @dfn{type-id} field value is a symbol. This symbol may be used by +the underlying base table implementation in storing that field. + +@noindent +If the @code{foreign-table} field is non-@code{#f} then that field names +a table from the catalog. The values for that domain must match a +primary key of the table referenced by the @var{type-param} (or +@code{#f}, if allowed). This package currently does not support +composite foreign-keys. + +@noindent +The types for which support is planned are: +@example +@group + atom + symbol + string [<length>] + number [<base>] + money <currency> + date-time + boolean + + foreign-key <table-name> + expression + virtual <expression> +@end group +@end example + +@node Unresolved Issues, Database Utilities, Catalog Representation, Relational Database +@subsection Unresolved Issues + +Although @file{rdms.scm} is not large I found it very difficult to write +(six rewrites). I am not aware of any other examples of a generalized +relational system (although there is little new in CS). I left out +several aspects of the Relational model in order to simplify the job. +The major features lacking (which might be addressed portably) are +views, transaction boundaries, and protection. + +Protection needs a model for specifying priveledges. Given how +operations are accessed from handles it should not be difficult to +restrict table accesses to those allowed for that user. + +The system catalog has a field called @code{view-procedure}. This +should allow a purely functional implementation of views. This will +work but is unsatisfying for views resulting from a @dfn{select}ion +(subset of rows); for whole table operations it will not be possible to +reduce the number of keys scanned over when the selection is specified +only by an opaque procedure. + +Transaction boundaries present the most intriguing area. Transaction +boundaries are actually a feature of the "Comprehensive Language" of the +Relational database and not of the database. Scheme would seem to +provide the opportunity for an extremely clean semantics for transaction +boundaries since the builtin procedures with side effects are small in +number and easily identified. + +These side-effect builtin procedures might all be portably redefined to +versions which properly handled transactions. Compiled library routines +would need to be recompiled as well. Many system extensions +(delete-file, system, etc.) would also need to be redefined. + +@noindent +There are 2 scope issues that must be resolved for multiprocess +transaction boundaries: + +@table @asis +@item Process scope +The actions captured by a transaction should be only for the process +which invoked the start of transaction. Although standard Scheme does +not provide process primitives as such, @code{dynamic-wind} would +provide a workable hook into process switching for many implementations. +@item Shared utilities with state +Some shared utilities have state which should @emph{not} be part of a +transaction. An example would be calling a pseudo-random number +generator. If the success of a transaction depended on the +pseudo-random number and failed, the state of the generator would be set +back. Subsequent calls would keep returning the same number and keep +failing. + +Pseudo-random number generators are not reentrant and so would require +locks in order to operate properly in a multiprocess environment. Are +all examples of utilities whose state should not part of transactions +also non-reentrant? If so, perhaps suspending transaction capture for +the duration of locks would fix it. +@end table + +@node Database Utilities, , Unresolved Issues, Relational Database +@subsection Database Utilities + +@code{(require 'database-utilities)} + +@noindent +This enhancement wraps a utility layer on @code{relational-database} +which provides: +@itemize @bullet +@item +Automatic loading of the appropriate base-table package when opening a +database. +@item +Automatic execution of initialization commands stored in database. +@item +Transparent execution of database commands stored in @code{*commands*} +table in database. +@end itemize + +@noindent +Also included are utilities which provide: +@itemize @bullet +@item +Data definition from Scheme lists and +@item +Report generation +@end itemize +@noindent +for any SLIB relational database. + +@defun create-database filename base-table-type +Returns an open, nearly empty enhanced (with @code{*commands*} table) +relational database (with base-table type @var{base-table-type}) +associated with @var{filename}. +@end defun + +@defun open-database filename +@defunx open-database filename base-table-type +Returns an open enchanced relational database associated with +@var{filename}. The database will be opened with base-table type +@var{base-table-type}) if supplied. If @var{base-table-type} is not +supplied, @code{open-database} will attempt to deduce the correct +base-table-type. If the database can not be opened or if it lacks the +@code{*commands*} table, @code{#f} is returned. + +@defunx open-database! filename +@defunx open-database! filename base-table-type +Returns @emph{mutable} open enchanced relational database @dots{} +@end defun + +@noindent +The table @code{*commands*} in an @dfn{enhanced} relational-database has +the fields (with domains): +@example +@group +PRI name symbol + parameters parameter-list + procedure expression + documentation string +@end group +@end example + +The @code{parameters} field is a foreign key (domain +@code{parameter-list}) of the @code{*catalog-data*} table and should +have the value of a table described by @code{*parameter-columns*}. This +@code{parameter-list} table describes the arguments suitable for passing +to the associated command. The intent of this table is to be of a form +such that different user-interfaces (for instance, pull-down menus or +plain-text queries) can operate from the same table. A +@code{parameter-list} table has the following fields: +@example +@group +PRI index uint + name symbol + arity parameter-arity + domain domain + default expression + documentation string +@end group +@end example + +The @code{arity} field can take the values: + +@table @code +@item single +Requires a single parameter of the specified domain. +@item optional +A single parameter of the specified domain or zero parameters is +acceptable. +@item boolean +A single boolean parameter or zero parameters (in which case @code{#f} +is substituted) is acceptable. +@item nary +Any number of parameters of the specified domain are acceptable. The +argument passed to the command function is always a list of the +parameters. +@item nary1 +One or more of parameters of the specified domain are acceptable. The +argument passed to the command function is always a list of the +parameters. +@end table + +The @code{domain} field specifies the domain which a parameter or +parameters in the @code{index}th field must satisfy. + +The @code{default} field is an expression whose value is either +@code{#f} or a procedure of no arguments which returns a parameter or +parameter list as appropriate. If the expression's value is @code{#f} +then no default is appropriate for this parameter. Note that since the +@code{default} procedure is called every time a default parameter is +needed for this column, @dfn{sticky} defaults can be implemented using +shared state with the domain-integrity-rule. + +@subsubheading Invoking Commands + +When an enhanced relational-database is called with a symbol which +matches a @var{name} in the @code{*commands*} table, the associated +procedure expression is evaluated and applied to the enhanced +relational-database. A procedure should then be returned which the user +can invoke on (optional) arguments. + +The command @code{*initialize*} is special. If present in the +@code{*commands*} table, @code{open-database} or @code{open-database!} +will return the value of the @code{*initialize*} command. Notice that +arbitrary code can be run when the @code{*initialize*} procedure is +automatically applied to the enhanced relational-database. + +Note also that if you wish to shadow or hide from the user +relational-database methods described in @ref{Relational Database +Operations}, this can be done by a dispatch in the closure returned by +the @code{*initialize*} expression rather than by entries in the +@code{*commands*} table if it is desired that the underlying methods +remain accessible to code in the @code{*commands*} table. + +@defun make-command-server rdb table-name +Returns a procedure of 2 arguments, a (symbol) command and a call-back +procedure. When this returned procedure is called, it looks up +@var{command} in table @var{table-name} and calls the call-back +procedure with arguments: +@table @var +@item command +The @var{command} +@item command-value +The result of evaluating the expression in the @var{procedure} field of +@var{table-name} and calling it with @var{rdb}. +@item parameter-name +A list of the @dfn{official} name of each parameter. Corresponds to the +@code{name} field of the @var{command}'s parameter-table. +@item positions +A list of the positive integer index of each parameter. Corresponds to +the @code{index} field of the @var{command}'s parameter-table. +@item arities +A list of the arities of each parameter. Corresponds to the +@code{arity} field of the @var{command}'s parameter-table. For a +description of @code{arity} see table above. +@item defaults +A list of the defaults for each parameter. Corresponds to +the @code{defaults} field of the @var{command}'s parameter-table. +@item domain-integrity-rules +A list of procedures (one for each parameter) which tests whether a +value for a parameter is acceptable for that parameter. The procedure +should be called with each datum in the list for @code{nary} arity +parameters. +@item aliases +A list of lists of @code{(@r{alias} @r{parameter-name})}. There can be +more than one alias per @var{parameter-name}. +@end table +@end defun + +For information about parameters, @xref{Parameter lists}. Here is an +example of setting up a command with arguments and parsing those +arguments from a @code{getopt} style argument list (@pxref{Getopt}). + +@example +(require 'database-utilities) +(require 'parameters) +(require 'getopt) + +(define my-rdb (create-database #f 'alist-table)) + +(define-tables my-rdb + '(foo-params + *parameter-columns* + *parameter-columns* + ((1 first-argument single string "hithere" "first argument") + (2 flag boolean boolean #f "a flag"))) + '(foo-pnames + ((name string)) + ((parameter-index uint)) + (("l" 1) + ("a" 2))) + '(my-commands + ((name symbol)) + ((parameters parameter-list) + (parameter-names parameter-name-translation) + (procedure expression) + (documentation string)) + ((foo + foo-params + foo-pnames + (lambda (rdb) (lambda (foo aflag) (print foo aflag))) + "test command arguments")))) + +(define (dbutil:serve-command-line rdb command-table + command argc argv) + (set! argv (if (vector? argv) (vector->list argv) argv)) + ((make-command-server rdb command-table) + command + (lambda (comname comval options positions + arities types defaults dirs aliases) + (apply comval (getopt->arglist argc argv options positions + arities types defaults dirs aliases))))) + +(define (test) + (set! *optind* 1) + (dbutil:serve-command-line + my-rdb 'my-commands 'foo 4 '("dummy" "-l" "foo" "-a"))) +(test) +@print{} +"foo" #t +@end example + +Some commands are defined in all extended relational-databases. The are +called just like @ref{Relational Database Operations}. + +@defun add-domain domain-row +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} +@end defun + +@defun delete-domain domain-name +Removes and returns the @var{domain-name} row from the @dfn{domains} +table. +@end defun + +@defun domain-checker domain +Returns a procedure to check an argument for conformance to domain +@var{domain}. +@end defun + +@subheading Defining Tables + +@deffn Procedure define-tables rdb spec-0 @dots{} +Adds tables as specified in @var{spec-0} @dots{} to the open +relational-database @var{rdb}. Each @var{spec} has the form: + +@lisp +(@r{<name>} @r{<descriptor-name>} @r{<descriptor-name>} @r{<rows>}) +@end lisp +or +@lisp +(@r{<name>} @r{<primary-key-fields>} @r{<other-fields>} @r{<rows>}) +@end lisp + +where @r{<name>} is the table name, @r{<descriptor-name>} is the symbol +name of a descriptor table, @r{<primary-key-fields>} and +@r{<other-fields>} describe the primary keys and other fields +respectively, and @r{<rows>} is a list of data rows to be added to the +table. + +@r{<primary-key-fields>} and @r{<other-fields>} are lists of field +descriptors of the form: + +@lisp +(@r{<column-name>} @r{<domain>}) +@end lisp +or +@lisp +(@r{<column-name>} @r{<domain>} @r{<column-integrity-rule>}) +@end lisp + +where @r{<column-name>} is the column name, @r{<domain>} is the domain +of the column, and @r{<column-integrity-rule>} is an expression whose +value is a procedure of one argument (and returns non-@code{#f} to +signal an error). + +If @r{<domain>} is not a defined domain name and it matches the name of +this table or an already defined (in one of @var{spec-0} @dots{}) single +key field table, a foriegn-key domain will be created for it. +@end deffn + + +@deffn Procedure create-report rdb destination report-name table +@deffnx Procedure create-report rdb destination report-name +The symbol @var{report-name} must be primary key in the table named +@code{*reports*} in the relational database @var{rdb}. +@var{destination} is a port, string, or symbol. If @var{destination} is +a: + +@table @asis +@item port +The table is created as ascii text and written to that port. +@item string +The table is created as ascii text and written to the file named by +@var{destination}. +@item symbol +@var{destination} is the primary key for a row in the table named *printers*. +@end table + +Each row in the table *reports* has the fields: + +@table @asis +@item name +The report name. +@item default-table +The table to report on if none is specified. +@item header, footer +A @code{format} string. At the beginning and end of each page +respectively, @code{format} is called with this string and the (list of) +column-names of this table. +@item reporter +A @code{format} string. For each row in the table, @code{format} is +called with this string and the row. +@item minimum-break +The minimum number of lines into which the report lines for a row can be +broken. Use @code{0} if a row's lines should not be broken over page +boundaries. +@end table + +Each row in the table *printers* has the fields: + +@table @asis +@item name +The printer name. +@item print-procedure +The procedure to call to actually print. +@end table + +The report is prepared as follows: + +@itemize +@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 + +@noindent +The following example shows a new database with the name of +@file{foo.db} being created with tables describing processor families +and processor/os/compiler combinations. + +@noindent +The database command @code{define-tables} is defined to call +@code{define-tables} with its arguments. The database is also +configured to print @samp{Welcome} when the database is opened. The +database is then closed and reopened. + +@example +(require 'database-utilities) +(define my-rdb (create-database "foo.db" 'alist-table)) + +(define-tables my-rdb + '(*commands* + ((name symbol)) + ((parameters parameter-list) + (procedure expression) + (documentation string)) + ((define-tables + no-parameters + no-parameter-names + (lambda (rdb) (lambda specs (apply define-tables rdb specs))) + "Create or Augment tables from list of specs") + (*initialize* + no-parameters + no-parameter-names + (lambda (rdb) (display "Welcome") (newline) rdb) + "Print Welcome")))) + +((my-rdb 'define-tables) + '(processor-family + ((family atom)) + ((also-ran processor-family)) + ((m68000 #f) + (m68030 m68000) + (i386 8086) + (8086 #f) + (powerpc #f))) + + '(platform + ((name symbol)) + ((processor processor-family) + (os symbol) + (compiler symbol)) + ((aix powerpc aix -) + (amiga-dice-c m68000 amiga dice-c) + (amiga-aztec m68000 amiga aztec) + (amiga-sas/c-5.10 m68000 amiga sas/c) + (atari-st-gcc m68000 atari gcc) + (atari-st-turbo-c m68000 atari turbo-c) + (borland-c-3.1 8086 ms-dos borland-c) + (djgpp i386 ms-dos gcc) + (linux i386 linux gcc) + (microsoft-c 8086 ms-dos microsoft-c) + (os/2-emx i386 os/2 gcc) + (turbo-c-2 8086 ms-dos turbo-c) + (watcom-9.0 i386 ms-dos watcom)))) + +((my-rdb 'close-database)) + +(set! my-rdb (open-database "foo.db" 'alist-table)) +@print{} +Welcome +@end example + +@node Weight-Balanced Trees, Structures, Relational Database, Data Structures +@section Weight-Balanced Trees + +@code{(require 'wt-tree)} + +@cindex trees, balanced binary +@cindex balanced binary trees +@cindex binary trees +@cindex weight-balanced binary trees +Balanced binary trees are a useful data structure for maintaining large +sets of ordered objects or sets of associations whose keys are ordered. +MIT Scheme has an comprehensive implementation of weight-balanced binary +trees which has several advantages over the other data structures for +large aggregates: + +@itemize @bullet +@item +In addition to the usual element-level operations like insertion, +deletion and lookup, there is a full complement of collection-level +operations, like set intersection, set union and subset test, all of +which are implemented with good orders of growth in time and space. +This makes weight balanced trees ideal for rapid prototyping of +functionally derived specifications. + +@item +An element in a tree may be indexed by its position under the ordering +of the keys, and the ordinal position of an element may be determined, +both with reasonable efficiency. + +@item +Operations to find and remove minimum element make weight balanced trees +simple to use for priority queues. + +@item +The implementation is @emph{functional} rather than @emph{imperative}. +This means that operations like `inserting' an association in a tree do +not destroy the old tree, in much the same way that @code{(+ 1 x)} +modifies neither the constant 1 nor the value bound to @code{x}. The +trees are referentially transparent thus the programmer need not worry +about copying the trees. Referential transparency allows space +efficiency to be achieved by sharing subtrees. + +@end itemize + +These features make weight-balanced trees suitable for a wide range of +applications, especially those that +require large numbers of sets or discrete maps. Applications that have +a few global databases and/or concentrate on element-level operations like +insertion and lookup are probably better off using hash-tables or +red-black trees. + +The @emph{size} of a tree is the number of associations that it +contains. Weight balanced binary trees are balanced to keep the sizes +of the subtrees of each node within a constant factor of each other. +This ensures logarithmic times for single-path operations (like lookup +and insertion). A weight balanced tree takes space that is proportional +to the number of associations in the tree. For the current +implementation, the constant of proportionality is six words per +association. + +@cindex binary trees, as sets +@cindex binary trees, as discrete maps +@cindex sets, using binary trees +@cindex discrete maps, using binary trees +Weight balanced trees can be used as an implementation for either +discrete sets or discrete maps (associations). Sets are implemented by +ignoring the datum that is associated with the key. Under this scheme +if an associations exists in the tree this indicates that the key of the +association is a member of the set. Typically a value such as +@code{()}, @code{#t} or @code{#f} is associated with the key. + +Many operations can be viewed as computing a result that, depending on +whether the tree arguments are thought of as sets or maps, is known by +two different names. +An example is @code{wt-tree/member?}, which, when +regarding the tree argument as a set, computes the set membership operation, but, +when regarding the tree as a discrete map, @code{wt-tree/member?} is the +predicate testing if the map is defined at an element in its domain. +Most names in this package have been chosen based on interpreting the +trees as sets, hence the name @code{wt-tree/member?} rather than +@code{wt-tree/defined-at?}. + + +@cindex run-time-loadable option +@cindex option, run-time-loadable +The weight balanced tree implementation is a run-time-loadable option. +To use weight balanced trees, execute + +@example +(load-option 'wt-tree) +@end example +@findex load-option + +@noindent +once before calling any of the procedures defined here. + + +@menu +* Construction of Weight-Balanced Trees:: +* Basic Operations on Weight-Balanced Trees:: +* Advanced Operations on Weight-Balanced Trees:: +* Indexing Operations on Weight-Balanced Trees:: +@end menu + +@node Construction of Weight-Balanced Trees, Basic Operations on Weight-Balanced Trees, Weight-Balanced Trees, Weight-Balanced Trees +@subsection Construction of Weight-Balanced Trees + +Binary trees require there to be a total order on the keys used to +arrange the elements in the tree. Weight balanced trees are organized +by @emph{types}, where the type is an object encapsulating the ordering +relation. Creating a tree is a two-stage process. First a tree type +must be created from the predicate which gives the ordering. The tree type +is then used for making trees, either empty or singleton trees or trees +from other aggregate structures like association lists. Once created, a +tree `knows' its type and the type is used to test compatibility between +trees in operations taking two trees. Usually a small number of tree +types are created at the beginning of a program and used many times +throughout the program's execution. + +@deffn {procedure+} make-wt-tree-type key<? +This procedure creates and returns a new tree type based on the ordering +predicate @var{key<?}. +@var{Key<?} must be a total ordering, having the property that for all +key values @code{a}, @code{b} and @code{c}: + +@example +(key<? a a) @result{} #f +(and (key<? a b) (key<? b a)) @result{} #f +(if (and (key<? a b) (key<? b c)) + (key<? a c) + #t) @result{} #t +@end example + +@noindent +Two key values are assumed to be equal if neither is less than the other +by @var{key<?}. + +Each call to @code{make-wt-tree-type} returns a distinct value, and +trees are only compatible if their tree types are @code{eq?}. +A consequence is +that trees that are intended to be used in binary tree operations must all be +created with a tree type originating from the same call to +@code{make-wt-tree-type}. +@end deffn + +@defvr {variable+} number-wt-type +A standard tree type for trees with numeric keys. @code{Number-wt-type} +could have been defined by + +@example +(define number-wt-type (make-wt-tree-type <)) +@end example +@end defvr + +@defvr {variable+} string-wt-type +A standard tree type for trees with string keys. @code{String-wt-type} +could have been defined by + +@example +(define string-wt-type (make-wt-tree-type string<?)) +@end example +@end defvr + + + +@deffn {procedure+} make-wt-tree wt-tree-type +This procedure creates and returns a newly allocated weight balanced +tree. The tree is empty, i.e. it contains no associations. +@var{Wt-tree-type} is a weight balanced tree type obtained by calling +@code{make-wt-tree-type}; the returned tree has this type. +@end deffn + +@deffn {procedure+} singleton-wt-tree wt-tree-type key datum +This procedure creates and returns a newly allocated weight balanced +tree. The tree contains a single association, that of @var{datum} with +@var{key}. @var{Wt-tree-type} is a weight balanced tree type obtained +by calling @code{make-wt-tree-type}; the returned tree has this type. +@end deffn + +@deffn {procedure+} alist->wt-tree tree-type alist +Returns a newly allocated weight-balanced tree that contains the same +associations as @var{alist}. This procedure is equivalent to: + +@example +(lambda (type alist) + (let ((tree (make-wt-tree type))) + (for-each (lambda (association) + (wt-tree/add! tree + (car association) + (cdr association))) + alist) + tree)) +@end example +@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 + +This section describes the basic tree operations on weight balanced +trees. These operations are the usual tree operations for insertion, +deletion and lookup, some predicates and a procedure for determining the +number of associations in a tree. + +@deffn {procedure+} wt-tree? object +Returns @code{#t} if @var{object} is a weight-balanced tree, otherwise +returns @code{#f}. +@end deffn + +@deffn {procedure+} wt-tree/empty? wt-tree +Returns @code{#t} if @var{wt-tree} contains no associations, otherwise +returns @code{#f}. +@end deffn + +@deffn {procedure+} wt-tree/size wt-tree +Returns the number of associations in @var{wt-tree}, an exact +non-negative integer. This operation takes constant time. +@end deffn + + +@deffn {procedure+} wt-tree/add wt-tree key datum +Returns a new tree containing all the associations in @var{wt-tree} and +the association of @var{datum} with @var{key}. If @var{wt-tree} already +had an association for @var{key}, the new association overrides the old. +The average and worst-case times required by this operation are +proportional to the logarithm of the number of associations in +@var{wt-tree}. +@end deffn + +@deffn {procedure+} wt-tree/add! wt-tree key datum +Associates @var{datum} with @var{key} in @var{wt-tree} and returns an +unspecified value. If @var{wt-tree} already has an association for +@var{key}, that association is replaced. The average and worst-case +times required by this operation are proportional to the logarithm of +the number of associations in @var{wt-tree}. +@end deffn + +@deffn {procedure+} wt-tree/member? key wt-tree +Returns @code{#t} if @var{wt-tree} contains an association for +@var{key}, otherwise returns @code{#f}. The average and worst-case +times required by this operation are proportional to the logarithm of +the number of associations in @var{wt-tree}. +@end deffn + +@deffn {procedure+} wt-tree/lookup wt-tree key default +Returns the datum associated with @var{key} in @var{wt-tree}. If +@var{wt-tree} doesn't contain an association for @var{key}, +@var{default} is returned. The average and worst-case times required by +this operation are proportional to the logarithm of the number of +associations in @var{wt-tree}. +@end deffn + +@deffn {procedure+} wt-tree/delete wt-tree key +Returns a new tree containing all the associations in @var{wt-tree}, +except that if @var{wt-tree} contains an association for @var{key}, it +is removed from the result. The average and worst-case times required +by this operation are proportional to the logarithm of the number of +associations in @var{wt-tree}. +@end deffn + +@deffn {procedure+} wt-tree/delete! wt-tree key +If @var{wt-tree} contains an association for @var{key} the association +is removed. Returns an unspecified value. The average and worst-case +times required by this operation are proportional to the logarithm of +the number of associations in @var{wt-tree}. +@end deffn + + +@node Advanced Operations on Weight-Balanced Trees, Indexing Operations on Weight-Balanced Trees, Basic Operations on Weight-Balanced Trees, Weight-Balanced Trees +@subsection Advanced Operations on Weight-Balanced Trees + +In the following the @emph{size} of a tree is the number of associations +that the tree contains, and a @emph{smaller} tree contains fewer +associations. + +@deffn {procedure+} wt-tree/split< wt-tree bound +Returns a new tree containing all and only the associations in +@var{wt-tree} which have a key that is less than @var{bound} in the +ordering relation of the tree type of @var{wt-tree}. The average and +worst-case times required by this operation are proportional to the +logarithm of the size of @var{wt-tree}. +@end deffn + +@deffn {procedure+} wt-tree/split> wt-tree bound +Returns a new tree containing all and only the associations in +@var{wt-tree} which have a key that is greater than @var{bound} in the +ordering relation of the tree type of @var{wt-tree}. The average and +worst-case times required by this operation are proportional to the +logarithm of size of @var{wt-tree}. +@end deffn + +@deffn {procedure+} wt-tree/union wt-tree-1 wt-tree-2 +Returns a new tree containing all the associations from both trees. +This operation is asymmetric: when both trees have an association for +the same key, the returned tree associates the datum from @var{wt-tree-2} +with the key. Thus if the trees are viewed as discrete maps then +@code{wt-tree/union} computes the map override of @var{wt-tree-1} by +@var{wt-tree-2}. If the trees are viewed as sets the result is the set +union of the arguments. +The worst-case time required by this operation +is proportional to the sum of the sizes of both trees. +If the minimum key of one tree is greater than the maximum key of +the other tree then the time required is at worst proportional to +the logarithm of the size of the larger tree. +@end deffn + +@deffn {procedure+} wt-tree/intersection wt-tree-1 wt-tree-2 +Returns a new tree containing all and only those associations from +@var{wt-tree-1} which have keys appearing as the key of an association +in @var{wt-tree-2}. Thus the associated data in the result are those +from @var{wt-tree-1}. If the trees are being used as sets the result is +the set intersection of the arguments. As a discrete map operation, +@code{wt-tree/intersection} computes the domain restriction of +@var{wt-tree-1} to (the domain of) @var{wt-tree-2}. +The time required by this operation is never worse that proportional to +the sum of the sizes of the trees. +@end deffn + +@deffn {procedure+} wt-tree/difference wt-tree-1 wt-tree-2 +Returns a new tree containing all and only those associations from +@var{wt-tree-1} which have keys that @emph{do not} appear as the key of +an association in @var{wt-tree-2}. If the trees are viewed as sets the +result is the asymmetric set difference of the arguments. As a discrete +map operation, it computes the domain restriction of @var{wt-tree-1} to +the complement of (the domain of) @var{wt-tree-2}. +The time required by this operation is never worse that proportional to +the sum of the sizes of the trees. +@end deffn + + +@deffn {procedure+} wt-tree/subset? wt-tree-1 wt-tree-2 +Returns @code{#t} iff the key of each association in @var{wt-tree-1} is +the key of some association in @var{wt-tree-2}, otherwise returns @code{#f}. +Viewed as a set operation, @code{wt-tree/subset?} is the improper subset +predicate. +A proper subset predicate can be constructed: + +@example +(define (proper-subset? s1 s2) + (and (wt-tree/subset? s1 s2) + (< (wt-tree/size s1) (wt-tree/size s2)))) +@end example + +As a discrete map operation, @code{wt-tree/subset?} is the subset +test on the domain(s) of the map(s). In the worst-case the time +required by this operation is proportional to the size of +@var{wt-tree-1}. +@end deffn + + +@deffn {procedure+} wt-tree/set-equal? wt-tree-1 wt-tree-2 +Returns @code{#t} iff for every association in @var{wt-tree-1} there is +an association in @var{wt-tree-2} that has the same key, and @emph{vice +versa}. + +Viewing the arguments as sets @code{wt-tree/set-equal?} is the set +equality predicate. As a map operation it determines if two maps are +defined on the same domain. + +This procedure is equivalent to + +@example +(lambda (wt-tree-1 wt-tree-2) + (and (wt-tree/subset? wt-tree-1 wt-tree-2 + (wt-tree/subset? wt-tree-2 wt-tree-1))) +@end example + +In the worst-case the time required by this operation is proportional to +the size of the smaller tree. +@end deffn + + +@deffn {procedure+} wt-tree/fold combiner initial wt-tree +This procedure reduces @var{wt-tree} by combining all the associations, +using an reverse in-order traversal, so the associations are visited in +reverse order. @var{Combiner} is a procedure of three arguments: a key, +a datum and the accumulated result so far. Provided @var{combiner} +takes time bounded by a constant, @code{wt-tree/fold} takes time +proportional to the size of @var{wt-tree}. + +A sorted association list can be derived simply: + +@example +(wt-tree/fold (lambda (key datum list) + (cons (cons key datum) list)) + '() + @var{wt-tree})) +@end example + +The data in the associations can be summed like this: + +@example +(wt-tree/fold (lambda (key datum sum) (+ sum datum)) + 0 + @var{wt-tree}) +@end example +@end deffn + +@deffn {procedure+} wt-tree/for-each action wt-tree +This procedure traverses the tree in-order, applying @var{action} to +each association. +The associations are processed in increasing order of their keys. +@var{Action} is a procedure of two arguments which take the key and +datum respectively of the association. +Provided @var{action} takes time bounded by a constant, +@code{wt-tree/for-each} takes time proportional to in the size of +@var{wt-tree}. +The example prints the tree: + +@example +(wt-tree/for-each (lambda (key value) + (display (list key value))) + @var{wt-tree})) +@end example +@end deffn + + +@node Indexing Operations on Weight-Balanced Trees, , Advanced Operations on Weight-Balanced Trees, Weight-Balanced Trees +@subsection Indexing Operations on Weight-Balanced Trees + +Weight balanced trees support operations that view the tree as sorted +sequence of associations. Elements of the sequence can be accessed by +position, and the position of an element in the sequence can be +determined, both in logarthmic time. + +@deffn {procedure+} wt-tree/index wt-tree index +@deffnx {procedure+} wt-tree/index-datum wt-tree index +@deffnx {procedure+} wt-tree/index-pair wt-tree index +Returns the 0-based @var{index}th association of @var{wt-tree} in the +sorted sequence under the tree's ordering relation on the keys. +@code{wt-tree/index} returns the @var{index}th key, +@code{wt-tree/index-datum} returns the datum associated with the +@var{index}th key and @code{wt-tree/index-pair} returns a new pair +@code{(@var{key} . @var{datum})} which is the @code{cons} of the @var{index}th +key and its datum. The average and worst-case times required by this +operation are proportional to the logarithm of the number of +associations in the tree. + +These operations signal an error if the tree is empty, if +@var{index}@code{<0}, or if @var{index} is greater than or equal to the +number of associations in the tree. + +Indexing can be used to find the median and maximum keys in the tree as +follows: + +@example +median: (wt-tree/index @var{wt-tree} (quotient (wt-tree/size @var{wt-tree}) 2)) + +maximum: (wt-tree/index @var{wt-tree} (-1+ (wt-tree/size @var{wt-tree}))) +@end example +@end deffn + +@deffn {procedure+} wt-tree/rank wt-tree key +Determines the 0-based position of @var{key} in the sorted sequence of +the keys under the tree's ordering relation, or @code{#f} if the tree +has no association with for @var{key}. This procedure returns either an +exact non-negative integer or @code{#f}. The average and worst-case +times required by this operation are proportional to the logarithm of +the number of associations in the tree. +@end deffn + +@deffn {procedure+} wt-tree/min wt-tree +@deffnx {procedure+} wt-tree/min-datum wt-tree +@deffnx {procedure+} wt-tree/min-pair wt-tree +Returns the association of @var{wt-tree} that has the least key under the tree's ordering relation. +@code{wt-tree/min} returns the least key, +@code{wt-tree/min-datum} returns the datum associated with the +least key and @code{wt-tree/min-pair} returns a new pair +@code{(key . datum)} which is the @code{cons} of the minimum key and its datum. +The average and worst-case times required by this operation are +proportional to the logarithm of the number of associations in the tree. + +These operations signal an error if the tree is empty. +They could be written +@example +(define (wt-tree/min tree) (wt-tree/index tree 0)) +(define (wt-tree/min-datum tree) (wt-tree/index-datum tree 0)) +(define (wt-tree/min-pair tree) (wt-tree/index-pair tree 0)) +@end example +@end deffn + +@deffn {procedure+} wt-tree/delete-min wt-tree +Returns a new tree containing all of the associations in @var{wt-tree} +except the association with the least key under the @var{wt-tree}'s +ordering relation. An error is signalled if the tree is empty. The +average and worst-case times required by this operation are proportional +to the logarithm of the number of associations in the tree. This +operation is equivalent to + +@example +(wt-tree/delete @var{wt-tree} (wt-tree/min @var{wt-tree})) +@end example +@end deffn + + +@deffn {procedure+} wt-tree/delete-min! wt-tree +Removes the association with the least key under the @var{wt-tree}'s +ordering relation. An error is signalled if the tree is empty. The +average and worst-case times required by this operation are proportional +to the logarithm of the number of associations in the tree. This +operation is equivalent to + +@example +(wt-tree/delete! @var{wt-tree} (wt-tree/min @var{wt-tree})) +@end example +@end deffn + + + +@node Structures, , Weight-Balanced Trees, Data Structures +@section Structures + +@code{(require 'struct)} (uses defmacros) + +@code{defmacro}s which implement @dfn{records} from the book +@cite{Essentials of Programming Languages} by Daniel P. Friedman, M. +Wand and C.T. Haynes. Copyright 1992 Jeff Alexander, Shinnder Lee, and +Lewis Patterson@refill + +Matthew McDonald <mafm@@cs.uwa.edu.au> added field setters. + +@defmac define-record tag (var1 var2 @dots{}) +Defines several functions pertaining to record-name @var{tag}: + +@defun make-@var{tag} var1 var2 @dots{} +@end defun +@defun @var{tag}? obj +@end defun +@defun @var{tag}->var1 obj +@end defun +@defun @var{tag}->var2 obj +@end defun +@dots{} +@defun set-@var{@var{tag}}-var1! obj val +@end defun +@defun set-@var{@var{tag}}-var2! obj val +@end defun +@dots{} + +Here is an example of its use. + +@example +(define-record term (operator left right)) +@result{} #<unspecified> +(define foo (make-term 'plus 1 2)) +@result{} foo +(term-left foo) +@result{} 1 +(set-term-left! foo 2345) +@result{} #<unspecified> +(term-left foo) +@result{} 2345 +@end example +@end defmac + +@defmac variant-case exp (tag (var1 var2 @dots{}) body) @dots{} +executes the following for the matching clause: + +@example +((lambda (@var{var1} @var{var} @dots{}) @var{body}) + (@var{tag->var1} @var{exp}) + (@var{tag->var2} @var{exp}) @dots{}) +@end example +@end defmac + +@node Macros, Numerics, Data Structures, Top +@chapter Macros +@menu +* Defmacro:: Supported by all implementations + +* R4RS Macros:: 'macro +* Macro by Example:: 'macro-by-example +* Macros That Work:: 'macros-that-work +* Syntactic Closures:: 'syntactic-closures +* Syntax-Case Macros:: 'syntax-case + +Syntax extensions (macros) included with SLIB. Also @xref{Structures}. + +* Fluid-Let:: 'fluid-let +* Yasos:: 'yasos, 'oop, 'collect +@end menu + + +@node Defmacro, R4RS Macros, Macros, Macros +@section Defmacro + +Defmacros are supported by all implementations. +@c See also @code{gentemp}, in @ref{Macros}. + +@defun gentemp +Returns a new (interned) symbol each time it is called. The symbol +names are implementation-dependent +@lisp +(gentemp) @result{} scm:G0 +(gentemp) @result{} scm:G1 +@end lisp +@end defun + +@defun defmacro:eval e +Returns the @code{slib:eval} of expanding all defmacros in scheme +expression @var{e}. +@end defun + +@defun defmacro:load filename +@var{filename} should be a string. If filename names an existing file, +the @code{defmacro:load} procedure reads Scheme source code expressions +and definitions from the file and evaluates them sequentially. These +source code expressions and definitions may contain defmacro +definitions. The @code{macro:load} procedure does not affect the values +returned by @code{current-input-port} and +@code{current-output-port}.@refill +@end defun + +@defun defmacro? sym +Returns @code{#t} if @var{sym} has been defined by @code{defmacro}, +@code{#f} otherwise. +@end defun + +@defun macroexpand-1 form +@defunx macroexpand form +If @var{form} is a macro call, @code{macroexpand-1} will expand the +macro call once and return it. A @var{form} is considered to be a macro +call only if it is a cons whose @code{car} is a symbol for which a +@code{defmacr} has been defined. + +@code{macroexpand} is similar to @code{macroexpand-1}, but repeatedly +expands @var{form} until it is no longer a macro call. +@end defun + +@defmac defmacro name lambda-list form @dots{} +When encountered by @code{defmacro:eval}, @code{defmacro:macroexpand*}, +or @code{defmacro:load} defines a new macro which will henceforth be +expanded when encountered by @code{defmacro:eval}, +@code{defmacro:macroexpand*}, or @code{defmacro:load}. +@end defmac + +@subsection Defmacroexpand +@code{(require 'defmacroexpand)} + +@defun defmacro:expand* e +Returns the result of expanding all defmacros in scheme expression +@var{e}. +@end defun + +@node R4RS Macros, Macro by Example, Defmacro, Macros +@section R4RS Macros + +@code{(require 'macro)} is the appropriate call if you want R4RS +high-level macros but don't care about the low level implementation. If +an SLIB R4RS macro implementation is already loaded it will be used. +Otherwise, one of the R4RS macros implemetations is loaded. + +The SLIB R4RS macro implementations support the following uniform +interface: + +@defun macro:expand sexpression +Takes an R4RS expression, macro-expands it, and returns the result of +the macro expansion. +@end defun + +@defun macro:eval sexpression +Takes an R4RS expression, macro-expands it, evals the result of the +macro expansion, and returns the result of the evaluation. +@end defun + +@deffn Procedure macro:load filename +@var{filename} should be a string. If filename names an existing file, +the @code{macro:load} procedure reads Scheme source code expressions and +definitions from the file and evaluates them sequentially. These source +code expressions and definitions may contain macro definitions. The +@code{macro:load} procedure does not affect the values returned by +@code{current-input-port} and @code{current-output-port}.@refill +@end deffn + +@node Macro by Example, Macros That Work, R4RS Macros, Macros +@section Macro by Example + +@code{(require 'macro-by-example)} + +A vanilla implementation of @cite{Macro by Example} (Eugene Kohlbecker, +R4RS) by Dorai Sitaram, (dorai@@cs.rice.edu) using @code{defmacro}. + +@itemize @bullet + +@item +generating hygienic global @code{define-syntax} Macro-by-Example macros +@strong{cheaply}. + +@item +can define macros which use @code{...}. + +@item +needn't worry about a lexical variable in a macro definition +clashing with a variable from the macro use context + +@item +don't suffer the overhead of redefining the repl if @code{defmacro} +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 +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 +variables with unintuitive bindings that the macro can't use. However, +if you must have the full @cite{r4rs} macro functionality, look to the +more featureful (but also more expensive) versions of syntax-rules +available in slib @ref{Macros That Work}, @ref{Syntactic Closures}, and +@ref{Syntax-Case Macros}. + +@defmac define-syntax keyword transformer-spec +The @var{keyword} is an identifier, and the @var{transformer-spec} +should be an instance of @code{syntax-rules}. + +The top-level syntactic environment is extended by binding the +@var{keyword} to the specified transformer. + +@example +(define-syntax let* + (syntax-rules () + ((let* () body1 body2 ...) + (let () body1 body2 ...)) + ((let* ((name1 val1) (name2 val2) ...) + body1 body2 ...) + (let ((name1 val1)) + (let* (( name2 val2) ...) + body1 body2 ...))))) +@end example +@end defmac + +@defmac syntax-rules literals syntax-rule @dots{} +@var{literals} is a list of identifiers, and each @var{syntax-rule} +should be of the form + +@code{(@var{pattern} @var{template})} + +where the @var{pattern} and @var{template} are as in the grammar above. + +An instance of @code{syntax-rules} produces a new macro transformer by +specifying a sequence of hygienic rewrite rules. A use of a macro whose +keyword is associated with a transformer specified by +@code{syntax-rules} is matched against the patterns contained in the +@var{syntax-rule}s, beginning with the leftmost @var{syntax-rule}. +When a match is found, the macro use is trancribed hygienically +according to the template. + +Each pattern begins with the keyword for the macro. This keyword is not +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, Macros +@section Macros That Work + +@code{(require 'macros-that-work)} + +@cite{Macros That Work} differs from the other R4RS macro +implementations in that it does not expand derived expression types to +primitive expression types. + +@defun macro:expand expression +@defunx macwork:expand expression +Takes an R4RS expression, macro-expands it, and returns the result of +the macro expansion. +@end defun + +@defun macro:eval expression +@defunx macwork:eval expression +@code{macro:eval} returns the value of @var{expression} in the current +top level environment. @var{expression} can contain macro definitions. +Side effects of @var{expression} will affect the top level +environment.@refill +@end defun + +@deffn Procedure macro:load filename +@deffnx Procedure macwork:load filename +@var{filename} should be a string. If filename names an existing file, +the @code{macro:load} procedure reads Scheme source code expressions and +definitions from the file and evaluates them sequentially. These source +code expressions and definitions may contain macro definitions. The +@code{macro:load} procedure does not affect the values returned by +@code{current-input-port} and @code{current-output-port}.@refill +@end deffn + +References: + +The @cite{Revised^4 Report on the Algorithmic Language Scheme} Clinger +and Rees [editors]. To appear in LISP Pointers. Also available as a +technical report from the University of Oregon, MIT AI Lab, and +Cornell.@refill + +@center Macros That Work. Clinger and Rees. POPL '91. + +The supported syntax differs from the R4RS in that vectors are allowed +as patterns and as templates and are not allowed as pattern or template +data. + +@example +transformer spec @expansion{} (syntax-rules literals rules) + +rules @expansion{} () + | (rule . rules) + +rule @expansion{} (pattern template) + +pattern @expansion{} pattern_var ; a symbol not in literals + | symbol ; a symbol in literals + | () + | (pattern . pattern) + | (ellipsis_pattern) + | #(pattern*) ; extends R4RS + | #(pattern* ellipsis_pattern) ; extends R4RS + | pattern_datum + +template @expansion{} pattern_var + | symbol + | () + | (template2 . template2) + | #(template*) ; extends R4RS + | pattern_datum + +template2 @expansion{} template + | ellipsis_template + +pattern_datum @expansion{} string ; no vector + | character + | boolean + | number + +ellipsis_pattern @expansion{} pattern ... + +ellipsis_template @expansion{} template ... + +pattern_var @expansion{} symbol ; not in literals + +literals @expansion{} () + | (symbol . literals) +@end example + +@subsection Definitions + +@table @asis + +@item Scope of an ellipsis +Within a pattern or template, the scope of an ellipsis (@code{...}) is +the pattern or template that appears to its left. + +@item Rank of a pattern variable +The rank of a pattern variable is the number of ellipses within whose +scope it appears in the pattern. + +@item Rank of a subtemplate +The rank of a subtemplate is the number of ellipses within whose scope +it appears in the template. + +@item Template rank of an occurrence of a pattern variable +The template rank of an occurrence of a pattern variable within a +template is the rank of that occurrence, viewed as a subtemplate. + +@item Variables bound by a pattern +The variables bound by a pattern are the pattern variables that appear +within it. + +@item Referenced variables of a subtemplate +The referenced variables of a subtemplate are the pattern variables that +appear within it. + +@item Variables opened by an ellipsis template +The variables opened by an ellipsis template are the referenced pattern +variables whose rank is greater than the rank of the ellipsis template. + +@end table + +@subsection Restrictions + +No pattern variable appears more than once within a pattern. + +For every occurrence of a pattern variable within a template, the +template rank of the occurrence must be greater than or equal to the +pattern variable's rank. + +Every ellipsis template must open at least one variable. + +For every ellipsis template, the variables opened by an ellipsis +template must all be bound to sequences of the same length. + +The compiled form of a @var{rule} is + +@example +rule @expansion{} (pattern template inserted) + +pattern @expansion{} pattern_var + | symbol + | () + | (pattern . pattern) + | ellipsis_pattern + | #(pattern) + | pattern_datum + +template @expansion{} pattern_var + | symbol + | () + | (template2 . template2) + | #(pattern) + | pattern_datum + +template2 @expansion{} template + | ellipsis_template + +pattern_datum @expansion{} string + | character + | boolean + | number + +pattern_var @expansion{} #(V symbol rank) + +ellipsis_pattern @expansion{} #(E pattern pattern_vars) + +ellipsis_template @expansion{} #(E template pattern_vars) + +inserted @expansion{} () + | (symbol . inserted) + +pattern_vars @expansion{} () + | (pattern_var . pattern_vars) + +rank @expansion{} exact non-negative integer +@end example + +where V and E are unforgeable values. + +The pattern variables associated with an ellipsis pattern are the +variables bound by the pattern, and the pattern variables associated +with an ellipsis template are the variables opened by the ellipsis +template. + +If the template contains a big chunk that contains no pattern variables +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, Macros +@section Syntactic Closures + +@code{(require 'syntactic-closures)} + +@defun macro:expand expression +@defunx synclo:expand expression +Returns scheme code with the macros and derived expression types of +@var{expression} expanded to primitive expression types.@refill +@end defun + +@defun macro:eval expression +@defunx synclo:eval expression +@code{macro:eval} returns the value of @var{expression} in the current +top level environment. @var{expression} can contain macro definitions. +Side effects of @var{expression} will affect the top level +environment.@refill +@end defun + +@deffn Procedure macro:load filename +@deffnx Procedure synclo:load filename +@var{filename} should be a string. If filename names an existing file, +the @code{macro:load} procedure reads Scheme source code expressions and +definitions from the file and evaluates them sequentially. These +source code expressions and definitions may contain macro definitions. +The @code{macro:load} procedure does not affect the values returned by +@code{current-input-port} and @code{current-output-port}.@refill +@end deffn + +@subsection Syntactic Closure Macro Facility + +@center A Syntactic Closures Macro Facility +@center by Chris Hanson +@center 9 November 1991 + +This document describes @dfn{syntactic closures}, a low-level macro +facility for the Scheme programming language. The facility is an +alternative to the low-level macro facility described in the +@cite{Revised^4 Report on Scheme.} This document is an addendum to that +report. + +The syntactic closures facility extends the BNF rule for +@var{transformer spec} to allow a new keyword that introduces a +low-level macro transformer:@refill +@example +@var{transformer spec} := (transformer @var{expression}) +@end example + +Additionally, the following procedures are added: +@lisp +make-syntactic-closure +capture-syntactic-environment +identifier? +identifier=? +@end lisp + +The description of the facility is divided into three parts. The first +part defines basic terminology. The second part describes how macro +transformers are defined. The third part describes the use of +@dfn{identifiers}, which extend the syntactic closure mechanism to be +compatible with @code{syntax-rules}.@refill + +@subsubsection Terminology + +This section defines the concepts and data types used by the syntactic +closures facility. + +@itemize + +@item @dfn{Forms} are the syntactic entities out of which programs are +recursively constructed. A form is any expression, any definition, any +syntactic keyword, or any syntactic closure. The variable name that +appears in a @code{set!} special form is also a form. Examples of +forms:@refill +@lisp +17 +#t +car +(+ x 4) +(lambda (x) x) +(define pi 3.14159) +if +define +@end lisp + +@item An @dfn{alias} is an alternate name for a given symbol. It can +appear anywhere in a form that the symbol could be used, and when quoted +it is replaced by the symbol; however, it does not satisfy the predicate +@code{symbol?}. Macro transformers rarely distinguish symbols from +aliases, referring to both as identifiers.@refill + +@item A @dfn{syntactic} environment maps identifiers to their +meanings. More precisely, it determines whether an identifier is a +syntactic keyword or a variable. If it is a keyword, the meaning is an +interpretation for the form in which that keyword appears. If it is a +variable, the meaning identifies which binding of that variable is +referenced. In short, syntactic environments contain all of the +contextual information necessary for interpreting the meaning of a +particular form.@refill + +@item A @dfn{syntactic closure} consists of a form, a syntactic +environment, and a list of identifiers. All identifiers in the form +take their meaning from the syntactic environment, except those in the +given list. The identifiers in the list are to have their meanings +determined later. A syntactic closure may be used in any context in +which its form could have been used. Since a syntactic closure is also +a form, it may not be used in contexts where a form would be illegal. +For example, a form may not appear as a clause in the cond special form. +A syntactic closure appearing in a quoted structure is replaced by its +form.@refill + +@end itemize + +@subsubsection Transformer Definition + +This section describes the @code{transformer} special form and the +procedures @code{make-syntactic-closure} and +@code{capture-syntactic-environment}.@refill + +@deffn Syntax transformer expression + +Syntax: It is an error if this syntax occurs except as a +@var{transformer spec}.@refill + +Semantics: The @var{expression} is evaluated in the standard transformer +environment to yield a macro transformer as described below. This macro +transformer is bound to a macro keyword by the special form in which the +@code{transformer} expression appears (for example, +@code{let-syntax}).@refill + +A @dfn{macro transformer} is a procedure that takes two arguments, a +form and a syntactic environment, and returns a new form. The first +argument, the @dfn{input form}, is the form in which the macro keyword +occurred. The second argument, the @dfn{usage environment}, is the +syntactic environment in which the input form occurred. The result of +the transformer, the @dfn{output form}, is automatically closed in the +@dfn{transformer environment}, which is the syntactic environment in +which the @code{transformer} expression occurred.@refill + +For example, here is a definition of a push macro using +@code{syntax-rules}:@refill +@lisp +(define-syntax push + (syntax-rules () + ((push item list) + (set! list (cons item list))))) +@end lisp + +Here is an equivalent definition using @code{transformer}: +@lisp +(define-syntax push + (transformer + (lambda (exp env) + (let ((item + (make-syntactic-closure env '() (cadr exp))) + (list + (make-syntactic-closure env '() (caddr exp)))) + `(set! ,list (cons ,item ,list)))))) +@end lisp + +In this example, the identifiers @code{set!} and @code{cons} are closed +in the transformer environment, and thus will not be affected by the +meanings of those identifiers in the usage environment +@code{env}.@refill + +Some macros may be non-hygienic by design. For example, the following +defines a loop macro that implicitly binds @code{exit} to an escape +procedure. The binding of @code{exit} is intended to capture free +references to @code{exit} in the body of the loop, so @code{exit} must +be left free when the body is closed:@refill +@lisp +(define-syntax loop + (transformer + (lambda (exp env) + (let ((body (cdr exp))) + `(call-with-current-continuation + (lambda (exit) + (let f () + ,@@(map (lambda (exp) + (make-syntactic-closure env '(exit) + exp)) + body) + (f)))))))) +@end lisp + +To assign meanings to the identifiers in a form, use +@code{make-syntactic-closure} to close the form in a syntactic +environment.@refill +@end deffn + +@defun make-syntactic-closure environment free-names form + +@var{environment} must be a syntactic environment, @var{free-names} must +be a list of identifiers, and @var{form} must be a form. +@code{make-syntactic-closure} constructs and returns a syntactic closure +of @var{form} in @var{environment}, which can be used anywhere that +@var{form} could have been used. All the identifiers used in +@var{form}, except those explicitly excepted by @var{free-names}, obtain +their meanings from @var{environment}.@refill + +Here is an example where @var{free-names} is something other than the +empty list. It is instructive to compare the use of @var{free-names} in +this example with its use in the @code{loop} example above: the examples +are similar except for the source of the identifier being left +free.@refill +@lisp +(define-syntax let1 + (transformer + (lambda (exp env) + (let ((id (cadr exp)) + (init (caddr exp)) + (exp (cadddr exp))) + `((lambda (,id) + ,(make-syntactic-closure env (list id) exp)) + ,(make-syntactic-closure env '() init)))))) +@end lisp + +@code{let1} is a simplified version of @code{let} that only binds a +single identifier, and whose body consists of a single expression. When +the body expression is syntactically closed in its original syntactic +environment, the identifier that is to be bound by @code{let1} must be +left free, so that it can be properly captured by the @code{lambda} in +the output form.@refill + +To obtain a syntactic environment other than the usage environment, use +@code{capture-syntactic-environment}.@refill +@end defun + +@defun capture-syntactic-environment procedure + +@code{capture-syntactic-environment} returns a form that will, when +transformed, call @var{procedure} on the current syntactic environment. +@var{procedure} should compute and return a new form to be transformed, +in that same syntactic environment, in place of the form.@refill + +An example will make this clear. Suppose we wanted to define a simple +@code{loop-until} keyword equivalent to@refill +@lisp +(define-syntax loop-until + (syntax-rules () + ((loop-until id init test return step) + (letrec ((loop + (lambda (id) + (if test return (loop step))))) + (loop init))))) +@end lisp + +The following attempt at defining @code{loop-until} has a subtle bug: +@lisp +(define-syntax loop-until + (transformer + (lambda (exp env) + (let ((id (cadr exp)) + (init (caddr exp)) + (test (cadddr exp)) + (return (cadddr (cdr exp))) + (step (cadddr (cddr exp))) + (close + (lambda (exp free) + (make-syntactic-closure env free exp)))) + `(letrec ((loop + (lambda (,id) + (if ,(close test (list id)) + ,(close return (list id)) + (loop ,(close step (list id))))))) + (loop ,(close init '()))))))) +@end lisp + +This definition appears to take all of the proper precautions to prevent +unintended captures. It carefully closes the subexpressions in their +original syntactic environment and it leaves the @code{id} identifier +free in the @code{test}, @code{return}, and @code{step} expressions, so +that it will be captured by the binding introduced by the @code{lambda} +expression. Unfortunately it uses the identifiers @code{if} and +@code{loop} within that @code{lambda} expression, so if the user of +@code{loop-until} just happens to use, say, @code{if} for the +identifier, it will be inadvertently captured.@refill + +The syntactic environment that @code{if} and @code{loop} want to be +exposed to is the one just outside the @code{lambda} expression: before +the user's identifier is added to the syntactic environment, but after +the identifier loop has been added. +@code{capture-syntactic-environment} captures exactly that environment +as follows:@refill +@lisp +(define-syntax loop-until + (transformer + (lambda (exp env) + (let ((id (cadr exp)) + (init (caddr exp)) + (test (cadddr exp)) + (return (cadddr (cdr exp))) + (step (cadddr (cddr exp))) + (close + (lambda (exp free) + (make-syntactic-closure env free exp)))) + `(letrec ((loop + ,(capture-syntactic-environment + (lambda (env) + `(lambda (,id) + (,(make-syntactic-closure env '() `if) + ,(close test (list id)) + ,(close return (list id)) + (,(make-syntactic-closure env '() + `loop) + ,(close step (list id))))))))) + (loop ,(close init '()))))))) +@end lisp + +In this case, having captured the desired syntactic environment, it is +convenient to construct syntactic closures of the identifiers @code{if} +and the @code{loop} and use them in the body of the +@code{lambda}.@refill + +A common use of @code{capture-syntactic-environment} is to get the +transformer environment of a macro transformer:@refill +@lisp +(transformer + (lambda (exp env) + (capture-syntactic-environment + (lambda (transformer-env) + ...)))) +@end lisp +@end defun + +@subsubsection Identifiers + +This section describes the procedures that create and manipulate +identifiers. Previous syntactic closure proposals did not have an +identifier data type -- they just used symbols. The identifier data +type extends the syntactic closures facility to be compatible with the +high-level @code{syntax-rules} facility.@refill + +As discussed earlier, an identifier is either a symbol or an +@dfn{alias}. An alias is implemented as a syntactic closure whose +@dfn{form} is an identifier:@refill +@lisp +(make-syntactic-closure env '() 'a) + @result{} an @dfn{alias} +@end lisp + +Aliases are implemented as syntactic closures because they behave just +like syntactic closures most of the time. The difference is that an +alias may be bound to a new value (for example by @code{lambda} or +@code{let-syntax}); other syntactic closures may not be used this way. +If an alias is bound, then within the scope of that binding it is looked +up in the syntactic environment just like any other identifier.@refill + +Aliases are used in the implementation of the high-level facility +@code{syntax-rules}. A macro transformer created by @code{syntax-rules} +uses a template to generate its output form, substituting subforms of +the input form into the template. In a syntactic closures +implementation, all of the symbols in the template are replaced by +aliases closed in the transformer environment, while the output form +itself is closed in the usage environment. This guarantees that the +macro transformation is hygienic, without requiring the transformer to +know the syntactic roles of the substituted input subforms. + +@defun identifier? object +Returns @code{#t} if @var{object} is an identifier, otherwise returns +@code{#f}. Examples:@refill +@lisp +(identifier? 'a) + @result{} #t +(identifier? (make-syntactic-closure env '() 'a)) + @result{} #t +(identifier? "a") + @result{} #f +(identifier? #\a) + @result{} #f +(identifier? 97) + @result{} #f +(identifier? #f) + @result{} #f +(identifier? '(a)) + @result{} #f +(identifier? '#(a)) + @result{} #f +@end lisp + +The predicate @code{eq?} is used to determine if two identifers are +``the same''. Thus @code{eq?} can be used to compare identifiers +exactly as it would be used to compare symbols. Often, though, it is +useful to know whether two identifiers ``mean the same thing''. For +example, the @code{cond} macro uses the symbol @code{else} to identify +the final clause in the conditional. A macro transformer for +@code{cond} cannot just look for the symbol @code{else}, because the +@code{cond} form might be the output of another macro transformer that +replaced the symbol @code{else} with an alias. Instead the transformer +must look for an identifier that ``means the same thing'' in the usage +environment as the symbol @code{else} means in the transformer +environment.@refill +@end defun + +@defun identifier=? environment1 identifier1 environment2 identifier2 +@var{environment1} and @var{environment2} must be syntactic +environments, and @var{identifier1} and @var{identifier2} must be +identifiers. @code{identifier=?} returns @code{#t} if the meaning of +@var{identifier1} in @var{environment1} is the same as that of +@var{identifier2} in @var{environment2}, otherwise it returns @code{#f}. +Examples:@refill + +@lisp +(let-syntax + ((foo + (transformer + (lambda (form env) + (capture-syntactic-environment + (lambda (transformer-env) + (identifier=? transformer-env 'x env 'x))))))) + (list (foo) + (let ((x 3)) + (foo)))) + @result{} (#t #f) +@end lisp + +@lisp +(let-syntax ((bar foo)) + (let-syntax + ((foo + (transformer + (lambda (form env) + (capture-syntactic-environment + (lambda (transformer-env) + (identifier=? transformer-env 'foo + env (cadr form)))))))) + (list (foo foo) + (foobar)))) + @result{} (#f #t) +@end lisp +@end defun + +@subsubsection Acknowledgements + +The syntactic closures facility was invented by Alan Bawden and Jonathan +Rees. The use of aliases to implement @code{syntax-rules} was invented +by Alan Bawden (who prefers to call them @dfn{synthetic names}). Much +of this proposal is derived from an earlier proposal by Alan +Bawden.@refill + + + + + +@node Syntax-Case Macros, Fluid-Let, Syntactic Closures, Macros +@section Syntax-Case Macros + +@code{(require 'syntax-case)} + +@defun macro:expand expression +@defunx syncase:expand expression +Returns scheme code with the macros and derived expression types of +@var{expression} expanded to primitive expression types.@refill +@end defun + +@defun macro:eval expression +@defunx syncase:eval expression +@code{macro:eval} returns the value of @var{expression} in the current +top level environment. @var{expression} can contain macro definitions. +Side effects of @var{expression} will affect the top level +environment.@refill +@end defun + +@deffn Procedure macro:load filename +@deffnx Procedure syncase:load filename +@var{filename} should be a string. If filename names an existing file, +the @code{macro:load} procedure reads Scheme source code expressions and +definitions from the file and evaluates them sequentially. These +source code expressions and definitions may contain macro definitions. +The @code{macro:load} procedure does not affect the values returned by +@code{current-input-port} and @code{current-output-port}.@refill +@end deffn + +This is version 2.1 of @code{syntax-case}, the low-level macro facility +proposed and implemented by Robert Hieb and R. Kent Dybvig. + +This version is further adapted by Harald Hanche-Olsen +<hanche@@imf.unit.no> to make it compatible with, and easily usable +with, SLIB. Mainly, these adaptations consisted of: + +@itemize @bullet +@item +Removing white space from @file{expand.pp} to save space in the +distribution. This file is not meant for human readers anyway@dots{} + +@item +Removed a couple of Chez scheme dependencies. + +@item +Renamed global variables used to minimize the possibility of name +conflicts. + +@item +Adding an SLIB-specific initialization file. + +@item +Removing a couple extra files, most notably the documentation (but see +below). +@end itemize + +If you wish, you can see exactly what changes were done by reading the +shell script in the file @file{syncase.sh}. + +The two PostScript files were omitted in order to not burden the SLIB +distribution with them. If you do intend to use @code{syntax-case}, +however, you should get these files and print them out on a PostScript +printer. They are available with the original @code{syntax-case} +distribution by anonymous FTP in +@file{cs.indiana.edu:/pub/scheme/syntax-case}.@refill + +In order to use syntax-case from an interactive top level, execute: +@lisp +(require 'syntax-case) +(require 'repl) +(repl:top-level macro:eval) +@end lisp +See the section Repl (@xref{Repl}) for more information. + +To check operation of syntax-case get +@file{cs.indiana.edu:/pub/scheme/syntax-case}, and type +@lisp +(require 'syntax-case) +(syncase:sanity-check) +@end lisp + +Beware that @code{syntax-case} takes a long time to load -- about 20s on +a SPARCstation SLC (with SCM) and about 90s on a Macintosh SE/30 (with +Gambit). + +@subsection Notes + +All R4RS syntactic forms are defined, including @code{delay}. Along +with @code{delay} are simple definitions for @code{make-promise} (into +which @code{delay} expressions expand) and @code{force}.@refill + +@code{syntax-rules} and @code{with-syntax} (described in @cite{TR356}) +are defined.@refill + +@code{syntax-case} is actually defined as a macro that expands into +calls to the procedure @code{syntax-dispatch} and the core form +@code{syntax-lambda}; do not redefine these names.@refill + +Several other top-level bindings not documented in TR356 are created: +@itemize +@item the ``hooks'' in @file{hooks.ss} +@item the @code{build-} procedures in @file{output.ss} +@item @code{expand-syntax} (the expander) +@end itemize + +The syntax of define has been extended to allow @code{(define @var{id})}, +which assigns @var{id} to some unspecified value.@refill + +We have attempted to maintain R4RS compatibility where possible. The +incompatibilities should be confined to @file{hooks.ss}. Please let us +know if there is some incompatibility that is not flagged as such.@refill + +Send bug reports, comments, suggestions, and questions to Kent Dybvig +(dyb@@iuvax.cs.indiana.edu). + +@subsection Note from maintainer + +Included with the @code{syntax-case} files was @file{structure.scm} +which defines a macro @code{define-structure}. There is no +documentation for this macro and it is not used by any code in SLIB. + +@node Fluid-Let, Yasos, Syntax-Case Macros, Macros +@section Fluid-Let + +@code{(require 'fluid-let)} + +@deffn Syntax fluid-let @code{(@var{bindings} @dots{})} @var{forms}@dots{} +@end deffn +@lisp +(fluid-let ((@var{variable} @var{init}) @dots{}) + @var{expression} @var{expression} @dots{}) +@end lisp + +The @var{init}s are evaluated in the current environment (in some +unspecified order), the current values of the @var{variable}s are saved, +the results are assigned to the @var{variable}s, the @var{expression}s +are evaluated sequentially in the current environment, the +@var{variable}s are restored to their original values, and the value of +the last @var{expression} is returned.@refill + +The syntax of this special form is similar to that of @code{let}, but +@code{fluid-let} temporarily rebinds existing @var{variable}s. Unlike +@code{let}, @code{fluid-let} creates no new bindings; instead it +@emph{assigns} the values of each @var{init} to the binding (determined +by the rules of lexical scoping) of its corresponding +@var{variable}.@refill + + +@node Yasos, , Fluid-Let, Macros +@section Yasos + +@c Much of the documentation in this section was written by Dave Love +@c (d.love@dl.ac.uk) -- don't blame Ken Dickey for its faults. +@c but we can blame him for not writing it! + +@code{(require 'oop)} or @code{(require 'yasos)} + +`Yet Another Scheme Object System' is a simple object system for Scheme +based on the paper by Norman Adams and Jonathan Rees: @cite{Object +Oriented Programming in Scheme}, Proceedings of the 1988 ACM Conference +on LISP and Functional Programming, July 1988 [ACM #552880].@refill + +Another reference is: + +Ken Dickey. +@ifset html +<A HREF="ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/swob.txt"> +@end ifset +Scheming with Objects +@ifset html +</A> +@end ifset +@cite{AI Expert} Volume 7, Number 10 (October 1992), pp. 24-33. + +@menu +* Yasos terms:: Definitions and disclaimer. +* Yasos interface:: The Yasos macros and procedures. +* Setters:: Dylan-like setters in Yasos. +* Yasos examples:: Usage of Yasos and setters. +@end menu + +@node Yasos terms, Yasos interface, Yasos, Yasos +@subsection Terms + +@table @asis +@item @dfn{Object} +Any Scheme data object. + +@item @dfn{Instance} +An instance of the OO system; an @dfn{object}. + +@item @dfn{Operation} +A @var{method}. +@end table + +@table @emph +@item Notes: +The object system supports multiple inheritance. An instance can +inherit from 0 or more ancestors. In the case of multiple inherited +operations with the same identity, the operation used is that from the +first ancestor which contains it (in the ancestor @code{let}). An +operation may be applied to any Scheme data object---not just instances. +As code which creates instances is just code, there are no @dfn{classes} +and no meta-@var{anything}. Method dispatch is by a procedure call a la +CLOS rather than by @code{send} syntax a la Smalltalk.@refill + +@item Disclaimer: +There are a number of optimizations which can be made. This +implementation is expository (although performance should be quite +reasonable). See the L&FP paper for some suggestions.@refill +@end table + + + + + +@node Yasos interface, Setters, Yasos terms, Yasos +@subsection Interface + +@deffn Syntax define-operation @code{(}opname self arg @dots{}@code{)} @var{default-body} +Defines a default behavior for data objects which don't handle the +operation @var{opname}. The default default behavior (for an empty +@var{default-body}) is to generate an error.@refill +@end deffn + +@deffn Syntax define-predicate opname? +Defines a predicate @var{opname?}, usually used for determining the +@dfn{type} of an object, such that @code{(@var{opname?} @var{object})} +returns @code{#t} if @var{object} has an operation @var{opname?} and +@code{#f} otherwise.@refill +@end deffn + +@deffn Syntax object @code{((@var{name} @var{self} @var{arg} @dots{}) @var{body})} @dots{} +Returns an object (an instance of the object system) with operations. +Invoking @code{(@var{name} @var{object} @var{arg} @dots{}} executes the +@var{body} of the @var{object} with @var{self} bound to @var{object} and +with argument(s) @var{arg}@dots{}.@refill +@end deffn + +@deffn Syntax object-with-ancestors @code{((}ancestor1 init1@code{)} @dots{}@code{)} operation @dots{} +A @code{let}-like form of @code{object} for multiple inheritance. It +returns an object inheriting the behaviour of @var{ancestor1} etc. An +operation will be invoked in an ancestor if the object itself does not +provide such a method. In the case of multiple inherited operations +with the same identity, the operation used is the one found in the first +ancestor in the ancestor list. +@end deffn + +@deffn Syntax operate-as component operation self arg @dots{} +Used in an operation definition (of @var{self}) to invoke the +@var{operation} in an ancestor @var{component} but maintain the object's +identity. Also known as ``send-to-super''.@refill +@end deffn + +@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{obj} preceded by @samp{#<INSTANCE>} for instances. +@end deffn + +@defun size obj +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 +@end defun + + + + + +@node Setters, Yasos examples, Yasos interface, Yasos +@subsection Setters + +@dfn{Setters} implement @dfn{generalized locations} for objects +associated with some sort of mutable state. A @dfn{getter} operation +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}). +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!}. + +This implementation of setters is similar to that in Dylan(TM) +(@cite{Dylan: An object-oriented dynamic language}, Apple Computer +Eastern Research and Technology). Common LISP provides similar +facilities through @code{setf}. + +@defun setter getter +Returns the setter for the procedure @var{getter}. E.g., since +@code{string-ref} is the getter corresponding to a setter which is +actually @code{string-set!}: +@example +(define foo "foo") +((setter string-ref) foo 0 #\F) ; set element 0 of foo +foo @result{} "Foo" +@end example +@end defun + +@deffn Syntax set place new-value +If @var{place} is a variable name, @code{set} is equivalent to +@code{set!}. Otherwise, @var{place} must have the form of a procedure +call, where the procedure name refers to a getter and the call indicates +an accessible generalized location, i.e., the call would return a value. +The return value of @code{set} is usually unspecified unless used with a +setter whose definition guarantees to return a useful value. +@example +(set (string-ref foo 2) #\O) ; generalized location with getter +foo @result{} "FoO" +(set foo "foo") ; like set! +foo @result{} "foo" +@end example +@end deffn + +@deffn Procedure add-setter getter setter +Add procedures @var{getter} and @var{setter} to the (inaccessible) list +of valid setter/getter pairs. @var{setter} implements the store +operation corresponding to the @var{getter} access operation for the +relevant state. The return value is unspecified. +@end deffn + +@deffn Procedure remove-setter-for getter +Removes the setter corresponding to the specified @var{getter} from the +list of valid setters. The return value is unspecified. +@end deffn + +@deffn Syntax define-access-operation getter-name +Shorthand for a Yasos @code{define-operation} defining an operation +@var{getter-name} that objects may support to return the value of some +mutable state. The default operation is to signal an error. The return +value is unspecified. +@end deffn + + + + + +@node Yasos examples, , Setters, Yasos +@subsection Examples + +@lisp +(define-operation (print obj port) + (format port + (if (instance? obj) "#<instance>" "~s") + obj)) + +(define-operation (SIZE obj) + (cond + ((vector? obj) (vector-length obj)) + ((list? obj) (length obj)) + ((pair? obj) 2) + ((string? obj) (string-length obj)) + ((char? obj) 1) + (else + (error "Operation not supported: size" obj)))) + +(define-predicate cell?) +(define-operation (fetch obj)) +(define-operation (store! obj newValue)) + +(define (make-cell value) + (object + ((cell? self) #t) + ((fetch self) value) + ((store! self newValue) + (set! value newValue) + newValue) + ((size self) 1) + ((print self port) + (format port "#<Cell: ~s>" (fetch self))))) + +(define-operation (discard obj value) + (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))))) + +(define-predicate array?) +(define-operation (array-ref array index)) +(define-operation (array-set! array index value)) + +(define (make-array num-slots) + (let ((anArray (make-vector num-slots))) + (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)))))) + +(define-operation (position obj)) +(define-operation (discarded-value obj)) + +(define (make-cell-with-history value filter size) + (let ((pos 0) (most-recent-discard #f)) + (object-with-ancestors + ((cell (make-filtered-call value filter)) + (sequence (make-array size))) + ((array? self) #f) + ((position self) pos) + ((store! self newValue) + (operate-as cell store! self newValue) + (array-set! self pos newValue) + (set! pos (+ pos 1))) + ((discard self value) + (set! most-recent-discard value)) + ((discarded-value self) most-recent-discard) + ((print self port) + (format port "#<Cell-with-history ~s>" (fetch self)))))) + +(define-access-operation fetch) +(add-setter fetch store!) +(define foo (make-cell 1)) +(print foo #f) +@result{} "#<Cell: 1>" +(set (fetch foo) 2) +@result{} +(print foo #f) +@result{} "#<Cell: 2>" +(fetch foo) +@result{} 2 +@end lisp + +@node Numerics, Procedures, Macros, Top +@chapter Numerics + +@menu +* Bit-Twiddling:: 'logical +* Modular Arithmetic:: 'modular +* Prime Testing and Generation:: 'primes +* Prime Factorization:: 'factor +* Random Numbers:: 'random +* Cyclic Checksum:: 'make-crc +* Plotting:: 'charplot +* Root Finding:: +@end menu + + +@node Bit-Twiddling, Modular Arithmetic, Numerics, Numerics +@section Bit-Twiddling + +@code{(require 'logical)} + +The bit-twiddling functions are made available through the use of the +@code{logical} package. @code{logical} is loaded by inserting +@code{(require 'logical)} before the code that uses these +functions.@refill + +@defun logand n1 n1 +Returns the integer which is the bit-wise AND of the two integer +arguments. + +Example: +@lisp +(number->string (logand #b1100 #b1010) 2) + @result{} "1000" +@end lisp +@end defun + +@defun logior n1 n2 +Returns the integer which is the bit-wise OR of the two integer +arguments. + +Example: +@lisp +(number->string (logior #b1100 #b1010) 2) + @result{} "1110" +@end lisp +@end defun + +@defun logxor n1 n2 +Returns the integer which is the bit-wise XOR of the two integer +arguments. + +Example: +@lisp +(number->string (logxor #b1100 #b1010) 2) + @result{} "110" +@end lisp +@end defun + +@defun lognot n +Returns the integer which is the 2s-complement of the integer argument. + +Example: +@lisp +(number->string (lognot #b10000000) 2) + @result{} "-10000001" +(number->string (lognot #b0) 2) + @result{} "-1" +@end lisp +@end defun + +@defun logtest j k +@example +(logtest j k) @equiv{} (not (zero? (logand j k))) + +(logtest #b0100 #b1011) @result{} #f +(logtest #b0100 #b0111) @result{} #t +@end example +@end defun + +@defun logbit? index j +@example +(logbit? index j) @equiv{} (logtest (integer-expt 2 index) j) + +(logbit? 0 #b1101) @result{} #t +(logbit? 1 #b1101) @result{} #f +(logbit? 2 #b1101) @result{} #t +(logbit? 3 #b1101) @result{} #t +(logbit? 4 #b1101) @result{} #f +@end example +@end defun + +@defun ash int count +Returns an integer equivalent to +@code{(inexact->exact (floor (* @var{int} (expt 2 @var{count}))))}.@refill + +Example: +@lisp +(number->string (ash #b1 3) 2) + @result{} "1000" +(number->string (ash #b1010 -1) 2) + @result{} "101" +@end lisp +@end defun + +@defun logcount 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, +0 is returned. + +Example: +@lisp +(logcount #b10101010) + @result{} 4 +(logcount 0) + @result{} 0 +(logcount -2) + @result{} 1 +@end lisp +@end defun + +@defun integer-length n +Returns the number of bits neccessary to represent @var{n}. + +Example: +@lisp +(integer-length #b10101010) + @result{} 8 +(integer-length 0) + @result{} 0 +(integer-length #b1111) + @result{} 4 +@end lisp +@end defun + +@defun integer-expt n k +Returns @var{n} raised to the non-negative integer exponent @var{k}. + +Example: +@lisp +(integer-expt 2 5) + @result{} 32 +(integer-expt -3 3) + @result{} -27 +@end lisp +@end defun + +@defun bit-extract n start end +Returns the integer composed of the @var{start} (inclusive) through +@var{end} (exclusive) bits of @var{n}. The @var{start}th bit becomes +the 0-th bit in the result.@refill + +Example: +@lisp +(number->string (bit-extract #b1101101010 0 4) 2) + @result{} "1010" +(number->string (bit-extract #b1101101010 4 9) 2) + @result{} "10110" +@end lisp +@end defun + + +@node Modular Arithmetic, Prime Testing and Generation, Bit-Twiddling, Numerics +@section Modular Arithmetic + +@code{(require 'modular)} + +@defun extended-euclid n1 n2 +Returns a list of 3 integers @code{(d x y)} such that d = gcd(@var{n1}, +@var{n2}) = @var{n1} * x + @var{n2} * y.@refill +@end defun + +@defun symmetric:modulus n +Returns @code{(quotient (+ -1 n) -2)} for positive odd integer @var{n}. +@end defun + +@defun modulus->integer modulus +Returns the non-negative integer characteristic of the ring formed when +@var{modulus} is used with @code{modular:} procedures. +@end defun + +@defun modular:normalize modulus n +Returns the integer @code{(modulo @var{n} (modulus->integer +@var{modulus}))} in the representation specified by @var{modulus}. +@end defun + +@noindent +The rest of these functions assume normalized arguments; That is, the +arguments are constrained by the following table: + +@noindent +For all of these functions, if the first argument (@var{modulus}) is: +@table @code +@item positive? +Work as before. The result is between 0 and @var{modulus}. + +@item zero? +The arguments are treated as integers. An integer is returned. + +@item negative? +The arguments and result are treated as members of the integers modulo +@code{(+ 1 (* -2 @var{modulus}))}, but with @dfn{symmetric} +representation; i.e. @code{(<= (- @var{modulus}) @var{n} +@var{modulus})}. +@end table + +@noindent +If all the arguments are fixnums the computation will use only fixnums. + +@defun modular:invertable? modulus k +Returns @code{#t} if there exists an integer n such that @var{k} * n +@equiv{} 1 mod @var{modulus}, and @code{#f} otherwise. +@end defun + +@defun modular:invert modulus k2 +Returns an integer n such that 1 = (n * @var{k2}) mod @var{modulus}. If +@var{k2} has no inverse mod @var{modulus} an error is signaled. +@end defun + +@defun modular:negate modulus k2 +Returns (@minus{}@var{k2}) mod @var{modulus}. +@end defun + +@defun modular:+ modulus k2 k3 +Returns (@var{k2} + @var{k3}) mod @var{modulus}. +@end defun + +@defun modular:@minus{} modulus k2 k3 +Returns (@var{k2} @minus{} @var{k3}) mod @var{modulus}. +@end defun + +@defun modular:* modulus k2 k3 +Returns (@var{k2} * @var{k3}) mod @var{modulus}. + +The Scheme code for @code{modular:*} with negative @var{modulus} is not +completed for fixnum-only implementations. +@end defun + +@defun modular:expt modulus k2 k3 +Returns (@var{k2} ^ @var{k3}) mod @var{modulus}. +@end defun + + +@node Prime Testing and Generation, Prime Factorization, Modular Arithmetic, Numerics +@section Prime Testing and Generation + +@code{(require 'primes)} + +This package tests and generates prime numbers. The strategy used is +as follows: + +@itemize +@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 + +@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, Numerics +@section Prime Factorization + +@code{(require 'factor)} + + +@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 + + + +@node Random Numbers, Cyclic Checksum, Prime Factorization, Numerics +@section Random Numbers + +@code{(require 'random)} + + +@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 + +@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 + +@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 support by the Scheme implementation, +@file{randinex.scm} will be loaded as well. @file{randinex.scm} +contains procedures for generating inexact distributions.@refill + +@deffn Procedure random:uniform state +Returns an uniformly distributed inexact real random number in the +range between 0 and 1. +@end deffn + +@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 + +@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 + +@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 + +@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 + +@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 + + +@node Cyclic Checksum, Plotting, Random Numbers, Numerics +@section Cyclic Checksum + +@code{(require 'make-crc)} + +@defun make-port-crc +@defunx make-port-crc degree +@defunx make-port-crc degree generator +Returns an expression for a procedure of one argument, a port. This +procedure reads characters from the port until the end of file and +returns the integer checksum of the bytes read. + +The integer @var{degree}, if given, specifies the degree of the +polynomial being computed -- which is also the number of bits computed +in the checksums. The default value is 32. + +The integer @var{generator} specifies the polynomial being computed. +The power of 2 generating each 1 bit is the exponent of a term of the +polynomial. The bit at position @var{degree} is implicit and should not +be part of @var{generator}. This allows systems with numbers limited to +32 bits to calculate 32 bit checksums. The default value of +@var{generator} when @var{degree} is 32 (its default) is: + +@example +(make-port-crc 32 #b00000100110000010001110110110111) +@end example + +Creates a procedure to calculate the P1003.2/D11.2 (POSIX.2) 32-bit +checksum from the polynomial: + +@example + 32 26 23 22 16 12 11 + ( x + x + x + x + x + x + x + + + 10 8 7 5 4 2 1 + x + x + x + x + x + x + x + 1 ) mod 2 +@end example +@end defun + +@example +(require 'make-crc) +(define crc32 (slib:eval (make-port-crc))) +(define (file-check-sum file) (call-with-input-file file crc32)) +(file-check-sum (in-vicinity (library-vicinity) "ratize.scm")) + +@result{} 3553047446 +@end example + +@node Plotting, Root Finding, Cyclic Checksum, Numerics +@section Plotting on Character Devices + +@code{(require 'charplot)} + +The plotting procedure is made available through the use of the +@code{charplot} package. @code{charplot} is loaded by inserting +@code{(require 'charplot)} before the code that uses this +procedure.@refill + +@defvar charplot:height +The number of rows to make the plot vertically. +@end defvar + +@defvar charplot:width +The number of columns to make the plot horizontally. +@end defvar + +@deffn Procedure plot! coords x-label y-label +@var{coords} is a list of pairs of x and y coordinates. @var{x-label} +and @var{y-label} are strings with which to label the x and y +axes.@refill + +Example: +@example +(require 'charplot) +(set! charplot:height 19) +(set! charplot:width 45) + +(define (make-points n) + (if (zero? n) + '() + (cons (cons (/ n 6) (sin (/ n 6))) (make-points (1- n))))) + +(plot! (make-points 37) "x" "Sin(x)") +@print{} +@group + Sin(x) ______________________________________________ + 1.25|- | + | | + 1|- **** | + | ** ** | + 750.0e-3|- * * | + | * * | + 500.0e-3|- * * | + | * | + 250.0e-3|- * | + | * * | + 0|-------------------*--------------------------| + | * | + -250.0e-3|- * * | + | * * | + -500.0e-3|- * | + | * * | + -750.0e-3|- * * | + | ** ** | + -1|- **** | + |____________:_____._____:_____._____:_________| + x 2 4 +@end group +@end example +@end deffn + + +@node Root Finding, , Plotting, Numerics +@section Root Finding + +@code{(require 'root)} + +@defun newtown: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 +@var{df/dx}(@var{x0}) is non-zero, returns an integer @var{x} for which +@var{f}(@var{x}) is closer to zero than either of the integers adjacent +to @var{x}; or returns @code{#f} if such an integer can't be found. + +To find the closest integer to a given integers square root: + +@example +(define (integer-sqrt y) + (newton:find-integer-root + (lambda (x) (- (* x x) y)) + (lambda (x) (* 2 x)) + (ash 1 (quotient (integer-length y) 2)))) + +(integer-sqrt 15) @result{} 4 +@end example +@end defun + +@defun integer-sqrt y +Given a non-negative integer @var{y}, returns the rounded square-root of +@var{y}. +@end defun + +@defun newton:find-root f df/dx x0 prec +Given real valued procedures @var{f}, @var{df/dx} of one (real) +argument, initial real value @var{x0} for which @var{df/dx}(@var{x0}) is +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} +returns the result of -@var{prec} iterations. +@end defun + +@noindent +H. J. Orchard, @cite{The Laguerre Method for Finding the Zeros of +Polynomials}, IEEE Transactions on Circuits and Systems, Vol. 36, +No. 11, November 1989, pp 1377-1381. + +@quotation +There are 2 errors in Orchard's Table II. Line k=2 for starting +value of 1000+j0 should have Z_k of 1.0475 + j4.1036 and line k=2 +for starting value of 0+j1000 should have Z_k of 1.0988 + j4.0833. +@end quotation + + +@defun laguerre:find-root f df/dz ddf/dz^2 z0 prec +Given complex valued procedure @var{f} of one (complex) argument, its +derivative (with respect to its argument) @var{df/dx}, its second +derivative @var{ddf/dz^2}, initial complex value @var{z0}, and 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, @code{laguerre:find-root} +returns the result of -@var{prec} iterations. +@end defun + +@defun laguerre:find-polynomial-root deg f df/dz ddf/dz^2 z0 prec +Given polynomial procedure @var{f} of integer degree @var{deg} of one +argument, its derivative (with respect to its argument) @var{df/dx}, its +second derivative @var{ddf/dz^2}, initial complex value @var{z0}, and +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, +@code{laguerre:find-polynomial-root} returns the result of -@var{prec} +iterations. +@end defun + + +@node Procedures, Standards Support, Numerics, Top +@chapter Procedures + +Anything that doesn't fall neatly into any of the other categories winds +up here. + +@menu +* Batch:: 'batch +* Common List Functions:: 'common-list-functions +* Format:: 'format +* Generic-Write:: 'generic-write +* Line I/O:: 'line-i/o +* Multi-Processing:: 'process +* Object-To-String:: 'object->string +* Pretty-Print:: 'pretty-print, 'pprint-file +* Sorting:: 'sort +* Topological Sort:: +* Standard Formatted I/O:: 'printf, 'scanf +* String-Case:: 'string-case +* String Ports:: 'string-port +* String Search:: +* Tektronix Graphics Support:: +* Tree Operations:: 'tree +@end menu + +@node Batch, Common List Functions, Procedures, Procedures +@section Batch + +@code{(require 'batch)} + +@noindent +The batch procedures provide a way to write and execute portable scripts +for a variety of operating systems. Each @code{batch:} procedure takes +as its first argument a parameter-list (@pxref{Parameter lists}). This +parameter-list argument @var{parms} contains named associations. Batch +currently uses 2 of these: + +@table @code +@item batch-port +The port on which to write lines of the batch file. +@item batch-dialect +The syntax of batch file to generate. Currently supported are: +@itemize @bullet +@item +unix +@item +dos +@item +vms +@item +system +@item +*unknown* +@end itemize +@end table + +@noindent +@file{batch.scm} uses 2 enhanced relational tables (@pxref{Database +Utilities}) to store information linking the names of +@code{operating-system}s to @code{batch-dialect}es. + +@defun batch:initialize! database +Defines @code{operating-system} and @code{batch-dialect} tables and adds +the domain @code{operating-system} to the enhanced relational database +@var{database}. +@end defun + +@defvar batch:platform +Is batch's best guess as to which operating-system it is running under. +@code{batch:platform} is set to @code{(software-type)} +(@pxref{Configuration}) unless @code{(software-type)} is @code{unix}, +in which case finer distinctions are made. +@end defvar + +@defun batch:call-with-output-script parms file proc +@var{proc} should be a procedure of one argument. If @var{file} is an +output-port, @code{batch:call-with-output-script} writes an appropriate +header to @var{file} and then calls @var{proc} with @var{file} as the +only argument. If @var{file} is a string, +@code{batch:call-with-output-script} opens a output-file of name +@var{file}, writes an appropriate header to @var{file}, and then calls +@var{proc} with the newly opened port as the only argument. Otherwise, +@code{batch:call-with-output-script} acts as if it was called with the +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 +has been added to @var{parms} or @code{(copy-tree @var{parms})} by the +code: + +@example +(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}. +@end defun + +@noindent +These functions return a non-false value if the command was successfully +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{} +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: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 +same for some operating systems (VMS). +@end defun + +@defun batch:comment parms line1 @dots{} +Writes comment lines @var{line1} @dots{} to the @code{batch-port} in +@var{parms}. +@end defun + +@defun batch:lines->file parms file line1 @dots{} +Writes commands to the @code{batch-port} in @var{parms} which create a +file named @var{file} with contents @var{line1} @dots{}. +@end defun + +@defun batch:delete-file parms file +Writes a command to the @code{batch-port} in @var{parms} which deletes +the file named @var{file}. +@end defun + +@defun batch:rename-file parms old-name new-name +Writes a command to the @code{batch-port} in @var{parms} which renames +the file @var{old-name} to @var{new-name}. +@end defun + +@noindent +In addition, batch provides some small utilities very useful for writing +scripts: + +@defun replace-suffix str old new +Returns a new string similar to @code{str} but with the suffix string +@var{old} removed and the suffix string @var{new} appended. If the end +of @var{str} does not match @var{old}, an error is signaled. +@end defun + +@defun string-join joiner string1 @dots{} +Returns a new string consisting of all the strings @var{string1} @dots{} +in order appended together with the string @var{joiner} between each +adjacent pair. +@end defun + +@defun must-be-first list1 list2 +Returns a new list consisting of the elements of @var{list2} ordered so +that if some elements of @var{list1} are @code{equal?} to elements of +@var{list2}, then those elements will appear first and in the order of +@var{list1}. +@end defun + +@defun must-be-last list1 list2 +Returns a new list consisting of the elements of @var{list1} ordered so +that if some elements of @var{list2} are @code{equal?} to elements of +@var{list1}, then those elements will appear last and in the order of +@var{list2}. +@end defun + +@defun os->batch-dialect osname +Returns its best guess for the @code{batch-dialect} to be used for the +operating-system named @var{osname}. @code{os->batch-dialect} uses the +tables added to @var{database} by @code{batch:initialize!}. +@end defun + +@noindent +Here is an example of the use of most of batch's procedures: + +@example +(require 'database-utilities) +(require 'parameters) +(require 'batch) + +(define batch (create-database #f 'alist-table)) +(batch:initialize! batch) + +(define my-parameters + (list (list 'batch-dialect (os->batch-dialect batch:platform)) + (list 'platform batch:platform) + (list 'batch-port (current-output-port)))) ;gets filled in later + +(batch:call-with-output-script + my-parameters + "my-batch" + (lambda (batch-port) + (adjoin-parameters! my-parameters (list 'batch-port batch-port)) + (and + (batch:comment my-parameters + "================ Write file with C program.") + (batch:rename-file my-parameters "hello.c" "hello.c~") + (batch:lines->file my-parameters "hello.c" + "#include <stdio.h>" + "int main(int argc, char **argv)" + "@{" + " printf(\"hello world\\n\");" + " return 0;" + "@}" ) + (batch:system my-parameters "cc" "-c" "hello.c") + (batch:system my-parameters "cc" "-o" "hello" + (replace-suffix "hello.c" ".c" ".o")) + (batch:system my-parameters "hello") + (batch:delete-file my-parameters "hello") + (batch:delete-file my-parameters "hello.c") + (batch:delete-file my-parameters "hello.o") + (batch:delete-file my-parameters "my-batch") + ))) +@end example + +@noindent +Produces the file @file{my-batch}: + +@example +#!/bin/sh +# "my-batch" build script created Sat Jun 10 21:20:37 1995 +# ================ Write file with C program. +mv -f hello.c hello.c~ +rm -f hello.c +echo '#include <stdio.h>'>>hello.c +echo 'int main(int argc, char **argv)'>>hello.c +echo '@{'>>hello.c +echo ' printf("hello world\n");'>>hello.c +echo ' return 0;'>>hello.c +echo '@}'>>hello.c +cc -c hello.c +cc -o hello hello.o +hello +rm -f hello +rm -f hello.c +rm -f hello.o +rm -f my-batch +@end example + +@noindent +When run, @file{my-batch} prints: + +@example +bash$ my-batch +mv: hello.c: No such file or directory +hello world +@end example + + +@node Common List Functions, Format, Batch, Procedures +@section Common List Functions + +@code{(require 'common-list-functions)} + +The procedures below follow the Common LISP equivalents apart from +optional arguments in some cases. + +@menu +* List construction:: +* Lists as sets:: +* Lists as sequences:: +* Destructive list operations:: +* Non-List functions:: +@end menu + + +@node List construction, Lists as sets, Common List Functions, Common List Functions +@subsection List construction + +@defun make-list k . init +@code{make-list} creates and returns a list of @var{k} elements. If +@var{init} is included, all elements in the list are initialized to +@var{init}.@refill + +Example: +@lisp +(make-list 3) + @result{} (#<unspecified> #<unspecified> #<unspecified>) +(make-list 5 'foo) + @result{} (foo foo foo foo foo) +@end lisp +@end defun + + +@defun list* x . y +Works like @code{list} except that the cdr of the last pair is the last +argument unless there is only one argument, when the result is just that +argument. Sometimes called @code{cons*}. E.g.:@refill +@lisp +(list* 1) + @result{} 1 +(list* 1 2 3) + @result{} (1 2 . 3) +(list* 1 2 '(3 4)) + @result{} (1 2 3 4) +(list* @var{args} '()) + @equiv{} (list @var{args}) +@end lisp +@end defun + +@defun copy-list lst +@code{copy-list} makes a copy of @var{lst} using new pairs and returns +it. Only the top level of the list is copied, i.e., pairs forming +elements of the copied list remain @code{eq?} to the corresponding +elements of the original; the copy is, however, not @code{eq?} to the +original, but is @code{equal?} to it.@refill + +Example: +@lisp +(copy-list '(foo foo foo)) + @result{} (foo foo foo) +(define q '(foo bar baz bang)) +(define p q) +(eq? p q) + @result{} #t +(define r (copy-list q)) +(eq? q r) + @result{} #f +(equal? q r) + @result{} #t +(define bar '(bar)) +(eq? bar (car (copy-list (list bar 'foo)))) +@result{} #t + @end lisp +@end defun + + + + + + +@node Lists as sets, Lists as sequences, List construction, Common List Functions +@subsection Lists as sets + +@code{eq?} is used to test for membership by all the procedures below +which treat lists as sets.@refill + +@defun adjoin e l +@code{adjoin} returns the adjoint of the element @var{e} and the list +@var{l}. That is, if @var{e} is in @var{l}, @code{adjoin} returns +@var{l}, otherwise, it returns @code{(cons @var{e} @var{l})}.@refill + +Example: +@lisp +(adjoin 'baz '(bar baz bang)) + @result{} (bar baz bang) +(adjoin 'foo '(bar baz bang)) + @result{} (foo bar baz bang) +@end lisp +@end defun + +@defun union l1 l2 +@code{union} returns the combination of @var{l1} and @var{l2}. +Duplicates between @var{l1} and @var{l2} are culled. Duplicates within +@var{l1} or within @var{l2} may or may not be removed.@refill + +Example: +@lisp +(union '(1 2 3 4) '(5 6 7 8)) + @result{} (4 3 2 1 5 6 7 8) +(union '(1 2 3 4) '(3 4 5 6)) + @result{} (2 1 3 4 5 6) +@end lisp +@end defun + +@defun intersection l1 l2 +@code{intersection} returns all elements that are in both @var{l1} and +@var{l2}.@refill + +Example: +@lisp +(intersection '(1 2 3 4) '(3 4 5 6)) + @result{} (3 4) +(intersection '(1 2 3 4) '(5 6 7 8)) + @result{} () +@end lisp +@end defun + +@defun set-difference l1 l2 +@code{set-difference} returns the union of all elements that are in +@var{l1} but not in @var{l2}.@refill + +Example: +@lisp +(set-difference '(1 2 3 4) '(3 4 5 6)) + @result{} (1 2) +(set-difference '(1 2 3 4) '(1 2 3 4 5 6)) + @result{} () +@end lisp +@end defun + +@defun member-if pred lst +@code{member-if} returns @var{lst} if @code{(@var{pred} @var{element})} +is @code{#t} for any @var{element} in @var{lst}. Returns @code{#f} if +@var{pred} does not apply to any @var{element} in @var{lst}.@refill + +Example: +@lisp +(member-if vector? '(1 2 3 4)) + @result{} #f +(member-if number? '(1 2 3 4)) + @result{} (1 2 3 4) +@end lisp +@end defun + +@defun some pred lst . more-lsts +@var{pred} is a boolean function of as many arguments as there are list +arguments to @code{some} i.e., @var{lst} plus any optional arguments. +@var{pred} is applied to successive elements of the list arguments in +order. @code{some} returns @code{#t} as soon as one of these +applications returns @code{#t}, and is @code{#f} if none returns +@code{#t}. All the lists should have the same length.@refill + + +Example: +@lisp +(some odd? '(1 2 3 4)) + @result{} #t + +(some odd? '(2 4 6 8)) + @result{} #f + +(some > '(2 3) '(1 4)) + @result{} #f +@end lisp +@end defun + +@defun every pred lst . more-lsts +@code{every} is analogous to @code{some} except it returns @code{#t} if +every application of @var{pred} is @code{#t} and @code{#f} +otherwise.@refill + +Example: +@lisp +(every even? '(1 2 3 4)) + @result{} #f + +(every even? '(2 4 6 8)) + @result{} #t + +(every > '(2 3) '(1 4)) + @result{} #f +@end lisp +@end defun + +@defun notany pred . lst +@code{notany} is analogous to @code{some} but returns @code{#t} if no +application of @var{pred} returns @code{#t} or @code{#f} as soon as any +one does.@refill +@end defun + +@defun notevery pred . lst +@code{notevery} is analogous to @code{some} but returns @code{#t} as soon +as an application of @var{pred} returns @code{#f}, and @code{#f} +otherwise.@refill + +Example: +@lisp +(notevery even? '(1 2 3 4)) + @result{} #t + +(notevery even? '(2 4 6 8)) + @result{} #f +@end lisp +@end defun + +@defun find-if pred lst +@code{find-if} searches for the first @var{element} in @var{lst} such +that @code{(@var{pred} @var{element})} returns @code{#t}. If it finds +any such @var{element} in @var{lst}, @var{element} is returned. +Otherwise, @code{#f} is returned.@refill + +Example: +@lisp +(find-if number? '(foo 1 bar 2)) + @result{} 1 + +(find-if number? '(foo bar baz bang)) + @result{} #f + +(find-if symbol? '(1 2 foo bar)) + @result{} foo +@end lisp +@end defun + +@defun remove elt lst +@code{remove} removes all occurrences of @var{elt} from @var{lst} using +@code{eqv?} to test for equality and returns everything that's left. +N.B.: other implementations (Chez, Scheme->C and T, at least) use +@code{equal?} as the equality test.@refill + +Example: +@lisp +(remove 1 '(1 2 1 3 1 4 1 5)) + @result{} (2 3 4 5) + +(remove 'foo '(bar baz bang)) + @result{} (bar baz bang) +@end lisp +@end defun + +@defun remove-if pred lst +@code{remove-if} removes all @var{element}s from @var{lst} where +@code{(@var{pred} @var{element})} is @code{#t} and returns everything +that's left.@refill + +Example: +@lisp +(remove-if number? '(1 2 3 4)) + @result{} () + +(remove-if even? '(1 2 3 4 5 6 7 8)) + @result{} (1 3 5 7) +@end lisp +@end defun + +@defun remove-if-not pred lst +@code{remove-if-not} removes all @var{element}s from @var{lst} for which +@code{(@var{pred} @var{element})} is @code{#f} and returns everything that's +left.@refill + +Example: +@lisp +(remove-if-not number? '(foo bar baz)) + @result{} () +(remove-if-not odd? '(1 2 3 4 5 6 7 8)) + @result{} (1 3 5 7) +@end lisp +@end defun + +@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)) + @result{} #f + +(has-duplicates? '(2 4 3 4)) + @result{} #t +@end lisp +@end defun + + +@node Lists as sequences, Destructive list operations, Lists as sets, Common List Functions +@subsection Lists as sequences + +@defun position obj lst +@code{position} returns the 0-based position of @var{obj} in @var{lst}, +or @code{#f} if @var{obj} does not occur in @var{lst}.@refill + +Example: +@lisp +(position 'foo '(foo bar baz bang)) + @result{} 0 +(position 'baz '(foo bar baz bang)) + @result{} 2 +(position 'oops '(foo bar baz bang)) + @result{} #f +@end lisp +@end defun + +@defun reduce p lst +@code{reduce} combines all the elements of a sequence using a binary +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} generalized to collections.@refill + +Example: +@lisp +(reduce + '(1 2 3 4)) + @result{} 10 +(define (bad-sum . l) (reduce + l)) +(bad-sum 1 2 3 4) + @equiv{} (reduce + (1 2 3 4)) + @equiv{} (+ (+ (+ 1 2) 3) 4) +@result{} 10 +(bad-sum) + @equiv{} (reduce + ()) + @result{} () +(reduce string-append '("hello" "cruel" "world")) + @equiv{} (string-append (string-append "hello" "cruel") "world") + @result{} "hellocruelworld" +(reduce anything '()) + @result{} () +(reduce anything '(x)) + @result{} x +@end lisp + +What follows is a rather non-standard implementation of @code{reverse} +in terms of @code{reduce} and a combinator elsewhere called +@dfn{C}.@refill + +@lisp +;;; Contributed by Jussi Piitulainen (jpiitula@@ling.helsinki.fi) + +(define commute + (lambda (f) + (lambda (x y) + (f y x)))) + +(define reverse + (lambda (args) + (reduce-init (commute cons) args))) +@end lisp +@end defun + +@defun reduce-init p init lst +@code{reduce-init} is the same as reduce, except that it implicitly +inserts @var{init} at the start of the list. @code{reduce-init} is +preferred if you want to handle the null list, the one-element, and +lists with two or more elements consistently. It is common to use the +operator's idempotent as the initializer. Functional programmers +usually call this @dfn{foldl}.@refill + +Example: +@lisp +(define (sum . l) (reduce-init + 0 l)) +(sum 1 2 3 4) + @equiv{} (reduce-init + 0 (1 2 3 4)) + @equiv{} (+ (+ (+ (+ 0 1) 2) 3) 4) + @result{} 10 +(sum) + @equiv{} (reduce-init + 0 '()) + @result{} 0 + +(reduce-init string-append "@@" '("hello" "cruel" "world")) +@equiv{} +(string-append (string-append (string-append "@@" "hello") + "cruel") + "world") +@result{} "@@hellocruelworld" +@end lisp + +Given a differentiation of 2 arguments, @code{diff}, the following will +differentiate by any number of variables. +@lisp +(define (diff* exp . vars) + (reduce-init diff exp vars)) +@end lisp + +Example: +@lisp +;;; Real-world example: Insertion sort using reduce-init. + +(define (insert l item) + (if (null? l) + (list item) + (if (< (car l) item) + (cons (car l) (insert (cdr l) item)) + (cons item l)))) +(define (insertion-sort l) (reduce-init insert '() l)) + +(insertion-sort '(3 1 4 1 5) + @equiv{} (reduce-init insert () (3 1 4 1 5)) + @equiv{} (insert (insert (insert (insert (insert () 3) 1) 4) 1) 5) + @equiv{} (insert (insert (insert (insert (3)) 1) 4) 1) 5) + @equiv{} (insert (insert (insert (1 3) 4) 1) 5) + @equiv{} (insert (insert (1 3 4) 1) 5) + @equiv{} (insert (1 1 3 4) 5) + @result{} (1 1 3 4 5) + @end lisp +@end defun + +@defun butlast lst n +@code{butlast} returns all but the last @var{n} elements of +@var{lst}.@refill + +Example: +@lisp +(butlast '(1 2 3 4) 3) + @result{} (1) +(butlast '(1 2 3 4) 4) + @result{} () +@end lisp +@end defun + +@defun nthcdr n lst +@code{nthcdr} takes @var{n} @code{cdr}s of @var{lst} and returns the +result. Thus @code{(nthcdr 3 @var{lst})} @equiv{} @code{(cdddr +@var{lst})} + +Example: +@lisp +(nthcdr 2 '(1 2 3 4)) + @result{} (3 4) +(nthcdr 0 '(1 2 3 4)) + @result{} (1 2 3 4) +@end lisp +@end defun + +@defun last lst n +@code{last} returns the last @var{n} elements of @var{lst}. @var{n} +must be a non-negative integer. + +Example: +@lisp +(last '(foo bar baz bang) 2) + @result{} (baz bang) +(last '(1 2 3) 0) + @result{} 0 +@end lisp +@end defun + + + + + + +@node Destructive list operations, Non-List functions, Lists as sequences, Common List Functions +@subsection Destructive list operations + +These procedures may mutate the list they operate on, but any such +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 + +Example: You want to find the subsets of a set. Here's the obvious way: + +@lisp +(define (subsets set) + (if (null? set) + '(()) + (append (mapcar (lambda (sub) (cons (car set) sub)) + (subsets (cdr set))) + (subsets (cdr set))))) +@end lisp +But that does way more consing than you need. Instead, you could +replace the @code{append} with @code{nconc}, since you don't have any +need for all the intermediate results.@refill + +Example: +@lisp +(define x '(a b c)) +(define y '(d e f)) +(nconc x y) + @result{} (a b c d e f) +x + @result{} (a b c d e f) +@end lisp + +@code{nconc} is the same as @code{append!} in @file{sc2.scm}. +@end deffn + +@deffn Procedure nreverse lst +@code{nreverse} reverses the order of elements in @var{lst} by mutating +@code{cdr}s of the list. Sometimes called @code{reverse!}.@refill + +Example: +@lisp +(define foo '(a b c)) +(nreverse foo) + @result{} (c b a) +foo + @result{} (a) +@end lisp + +Some people have been confused about how to use @code{nreverse}, +thinking that it doesn't return a value. It needs to be pointed out +that@refill +@lisp +(set! lst (nreverse lst)) +@end lisp +@noindent +is the proper usage, not +@lisp +(nreverse lst) +@end lisp +The example should suffice to show why this is the case. +@end deffn + +@deffn Procedure delete elt lst +@deffnx Procedure delete-if pred lst +@deffnx Procedure delete-if-not pred lst +Destructive versions of @code{remove} @code{remove-if}, and +@code{remove-if-not}.@refill + +Example: +@lisp +(define lst '(foo bar baz bang)) +(delete 'foo lst) + @result{} (bar baz bang) +lst + @result{} (foo bar baz bang) + +(define lst '(1 2 3 4 5 6 7 8 9)) +(delete-if odd? lst) + @result{} (2 4 6 8) +lst + @result{} (1 2 4 6 8) +@end lisp + +Some people have been confused about how to use @code{delete}, +@code{delete-if}, and @code{delete-if}, thinking that they dont' return +a value. It needs to be pointed out that@refill +@lisp +(set! lst (delete el lst)) +@end lisp +@noindent +is the proper usage, not +@lisp +(delete el lst) +@end lisp +The examples should suffice to show why this is the case. +@end deffn + + + +@node Non-List functions, , Destructive list operations, Common List Functions +@subsection Non-List functions + +@defun and? . args +@code{and?} checks to see if all its arguments are true. If they are, +@code{and?} returns @code{#t}, otherwise, @code{#f}. (In contrast to +@code{and}, this is a function, so all arguments are always evaluated +and in an unspecified order.)@refill + +Example: +@lisp +(and? 1 2 3) + @result{} #t +(and #f 1 2) + @result{} #f +@end lisp +@end defun + +@defun or? . args +@code{or?} checks to see if any of its arguments are true. If any is +true, @code{or?} returns @code{#t}, and @code{#f} otherwise. (To +@code{or} as @code{and?} is to @code{and}.)@refill + +Example: +@lisp +(or? 1 2 #f) + @result{} #t +(or? #f #f #f) + @result{} #f +@end lisp +@end defun + +@defun atom? object +Returns @code{#t} if @var{object} is not a pair and @code{#f} if it is +pair. (Called @code{atom} in Common LISP.) +@lisp +(atom? 1) + @result{} #t +(atom? '(1 2)) + @result{} #f +(atom? #(1 2)) ; dubious! + @result{} #t +@end lisp +@end defun + +@defun type-of object +Returns a symbol name for the type of @var{object}. +@end defun + +@defun coerce object result-type +Converts and returns @var{object} of type @code{char}, @code{number}, +@code{string}, @code{symbol}, @code{list}, or @code{vector} to +@var{result-type} (which must be one of these symbols). +@end defun + +@node Format, Generic-Write, Common List Functions, Procedures +@section Format + +@code{(require 'format)} + +@menu +* Format Interface:: +* Format Specification:: +@end menu + +@node Format Interface, Format Specification, Format, Format +@subsection Format Interface + +@defun format destination format-string . arguments +An almost complete implementation of Common LISP format description +according to the CL reference book @cite{Common LISP} from Guy L. +Steele, Digital Press. Backward compatible to most of the available +Scheme format implementations. + +Returns @code{#t}, @code{#f} or a string; has side effect of printing +according to @var{format-string}. If @var{destination} is @code{#t}, +the output is to the current output port and @code{#t} is returned. If +@var{destination} is @code{#f}, a formatted string is returned as the +result of the call. NEW: If @var{destination} is a string, +@var{destination} is regarded as the format string; @var{format-string} is +then the first argument and the output is returned as a string. If +@var{destination} is a number, the output is to the current error port +if available by the implementation. Otherwise @var{destination} must be +an output port and @code{#t} is returned.@refill + +@var{format-string} must be a string. In case of a formatting error +format returns @code{#f} and prints a message on the current output or +error port. Characters are output as if the string were output by the +@code{display} function with the exception of those prefixed by a tilde +(~). For a detailed description of the @var{format-string} syntax +please consult a Common LISP format reference manual. For a test suite +to verify this format implementation load @file{formatst.scm}. Please +send bug reports to @code{lutzeb@@cs.tu-berlin.de}. + +Note: @code{format} is not reentrant, i.e. only one @code{format}-call +may be executed at a time. + +@end defun + +@node Format Specification, , Format Interface, Format +@subsection Format Specification (Format version 3.0) + +Please consult a Common LISP format reference manual for a detailed +description of the format string syntax. For a demonstration of the +implemented directives see @file{formatst.scm}.@refill + +This implementation supports directive parameters and modifiers +(@code{:} and @code{@@} characters). Multiple parameters must be +separated by a comma (@code{,}). Parameters can be numerical parameters +(positive or negative), character parameters (prefixed by a quote +character (@code{'}), variable parameters (@code{v}), number of rest +arguments parameter (@code{#}), empty and default parameters. Directive +characters are case independent. The general form of a directive +is:@refill + +@noindent +@var{directive} ::= ~@{@var{directive-parameter},@}[:][@@]@var{directive-character} + +@noindent +@var{directive-parameter} ::= [ [-|+]@{0-9@}+ | '@var{character} | v | # ] + + +@subsubsection Implemented CL Format Control Directives + +Documentation syntax: Uppercase characters represent the corresponding +control directive characters. Lowercase characters represent control +directive parameter descriptions. + +@table @asis +@item @code{~A} +Any (print as @code{display} does). +@table @asis +@item @code{~@@A} +left pad. +@item @code{~@var{mincol},@var{colinc},@var{minpad},@var{padchar}A} +full padding. +@end table +@item @code{~S} +S-expression (print as @code{write} does). +@table @asis +@item @code{~@@S} +left pad. +@item @code{~@var{mincol},@var{colinc},@var{minpad},@var{padchar}S} +full padding. +@end table +@item @code{~D} +Decimal. +@table @asis +@item @code{~@@D} +print number sign always. +@item @code{~:D} +print comma separated. +@item @code{~@var{mincol},@var{padchar},@var{commachar}D} +padding. +@end table +@item @code{~X} +Hexadecimal. +@table @asis +@item @code{~@@X} +print number sign always. +@item @code{~:X} +print comma separated. +@item @code{~@var{mincol},@var{padchar},@var{commachar}X} +padding. +@end table +@item @code{~O} +Octal. +@table @asis +@item @code{~@@O} +print number sign always. +@item @code{~:O} +print comma separated. +@item @code{~@var{mincol},@var{padchar},@var{commachar}O} +padding. +@end table +@item @code{~B} +Binary. +@table @asis +@item @code{~@@B} +print number sign always. +@item @code{~:B} +print comma separated. +@item @code{~@var{mincol},@var{padchar},@var{commachar}B} +padding. +@end table +@item @code{~@var{n}R} +Radix @var{n}. +@table @asis +@item @code{~@var{n},@var{mincol},@var{padchar},@var{commachar}R} +padding. +@end table +@item @code{~@@R} +print a number as a Roman numeral. +@item @code{~:R} +print a number as an ordinal English number. +@item @code{~:@@R} +print a number as a cardinal English number. +@item @code{~P} +Plural. +@table @asis +@item @code{~@@P} +prints @code{y} and @code{ies}. +@item @code{~:P} +as @code{~P but jumps 1 argument backward.} +@item @code{~:@@P} +as @code{~@@P but jumps 1 argument backward.} +@end table +@item @code{~C} +Character. +@table @asis +@item @code{~@@C} +prints a character as the reader can understand it (i.e. @code{#\} prefixing). +@item @code{~:C} +prints a character as emacs does (eg. @code{^C} for ASCII 03). +@end table +@item @code{~F} +Fixed-format floating-point (prints a flonum like @var{mmm.nnn}). +@table @asis +@item @code{~@var{width},@var{digits},@var{scale},@var{overflowchar},@var{padchar}F} +@item @code{~@@F} +If the number is positive a plus sign is printed. +@end table +@item @code{~E} +Exponential floating-point (prints a flonum like @var{mmm.nnn@code{E}ee}). +@table @asis +@item @code{~@var{width},@var{digits},@var{exponentdigits},@var{scale},@var{overflowchar},@var{padchar},@var{exponentchar}E} +@item @code{~@@E} +If the number is positive a plus sign is printed. +@end table +@item @code{~G} +General floating-point (prints a flonum either fixed or exponential). +@table @asis +@item @code{~@var{width},@var{digits},@var{exponentdigits},@var{scale},@var{overflowchar},@var{padchar},@var{exponentchar}G} +@item @code{~@@G} +If the number is positive a plus sign is printed. +@end table +@item @code{~$} +Dollars floating-point (prints a flonum in fixed with signs separated). +@table @asis +@item @code{~@var{digits},@var{scale},@var{width},@var{padchar}$} +@item @code{~@@$} +If the number is positive a plus sign is printed. +@item @code{~:@@$} +A sign is always printed and appears before the padding. +@item @code{~:$} +The sign appears before the padding. +@end table +@item @code{~%} +Newline. +@table @asis +@item @code{~@var{n}%} +print @var{n} newlines. +@end table +@item @code{~&} +print newline if not at the beginning of the output line. +@table @asis +@item @code{~@var{n}&} +prints @code{~&} and then @var{n-1} newlines. +@end table +@item @code{~|} +Page Separator. +@table @asis +@item @code{~@var{n}|} +print @var{n} page separators. +@end table +@item @code{~~} +Tilde. +@table @asis +@item @code{~@var{n}~} +print @var{n} tildes. +@end table +@item @code{~}<newline> +Continuation Line. +@table @asis +@item @code{~:}<newline> +newline is ignored, white space left. +@item @code{~@@}<newline> +newline is left, white space ignored. +@end table +@item @code{~T} +Tabulation. +@table @asis +@item @code{~@@T} +relative tabulation. +@item @code{~@var{colnum,colinc}T} +full tabulation. +@end table +@item @code{~?} +Indirection (expects indirect arguments as a list). +@table @asis +@item @code{~@@?} +extracts indirect arguments from format arguments. +@end table +@item @code{~(@var{str}~)} +Case conversion (converts by @code{string-downcase}). +@table @asis +@item @code{~:(@var{str}~)} +converts by @code{string-capitalize}. +@item @code{~@@(@var{str}~)} +converts by @code{string-capitalize-first}. +@item @code{~:@@(@var{str}~)} +converts by @code{string-upcase}. +@end table +@item @code{~*} +Argument Jumping (jumps 1 argument forward). +@table @asis +@item @code{~@var{n}*} +jumps @var{n} arguments forward. +@item @code{~:*} +jumps 1 argument backward. +@item @code{~@var{n}:*} +jumps @var{n} arguments backward. +@item @code{~@@*} +jumps to the 0th argument. +@item @code{~@var{n}@@*} +jumps to the @var{n}th argument (beginning from 0) +@end table +@item @code{~[@var{str0}~;@var{str1}~;...~;@var{strn}~]} +Conditional Expression (numerical clause conditional). +@table @asis +@item @code{~@var{n}[} +take argument from @var{n}. +@item @code{~@@[} +true test conditional. +@item @code{~:[} +if-else-then conditional. +@item @code{~;} +clause separator. +@item @code{~:;} +default clause follows. +@end table +@item @code{~@{@var{str}~@}} +Iteration (args come from the next argument (a list)). +@table @asis +@item @code{~@var{n}@{} +at most @var{n} iterations. +@item @code{~:@{} +args from next arg (a list of lists). +@item @code{~@@@{} +args from the rest of arguments. +@item @code{~:@@@{} +args from the rest args (lists). +@end table +@item @code{~^} +Up and out. +@table @asis +@item @code{~@var{n}^} +aborts if @var{n} = 0 +@item @code{~@var{n},@var{m}^} +aborts if @var{n} = @var{m} +@item @code{~@var{n},@var{m},@var{k}^} +aborts if @var{n} <= @var{m} <= @var{k} +@end table +@end table + + +@subsubsection Not Implemented CL Format Control Directives + +@table @asis +@item @code{~:A} +print @code{#f} as an empty list (see below). +@item @code{~:S} +print @code{#f} as an empty list (see below). +@item @code{~<~>} +Justification. +@item @code{~:^} +(sorry I don't understand its semantics completely) +@end table + + +@subsubsection Extended, Replaced and Additional Control Directives + +@table @asis +@item @code{~@var{mincol},@var{padchar},@var{commachar},@var{commawidth}D} +@item @code{~@var{mincol},@var{padchar},@var{commachar},@var{commawidth}X} +@item @code{~@var{mincol},@var{padchar},@var{commachar},@var{commawidth}O} +@item @code{~@var{mincol},@var{padchar},@var{commachar},@var{commawidth}B} +@item @code{~@var{n},@var{mincol},@var{padchar},@var{commachar},@var{commawidth}R} +@var{commawidth} is the number of characters between two comma characters. +@end table + +@table @asis +@item @code{~I} +print a R4RS complex number as @code{~F~@@Fi} with passed parameters for +@code{~F}. +@item @code{~Y} +Pretty print formatting of an argument for scheme code lists. +@item @code{~K} +Same as @code{~?.} +@item @code{~!} +Flushes the output if format @var{destination} is a port. +@item @code{~_} +Print a @code{#\space} character +@table @asis +@item @code{~@var{n}_} +print @var{n} @code{#\space} characters. +@end table +@item @code{~/} +Print a @code{#\tab} character +@table @asis +@item @code{~@var{n}/} +print @var{n} @code{#\tab} characters. +@end table +@item @code{~@var{n}C} +Takes @var{n} as an integer representation for a character. No arguments +are consumed. @var{n} is converted to a character by +@code{integer->char}. @var{n} must be a positive decimal number.@refill +@item @code{~:S} +Print out readproof. Prints out internal objects represented as +@code{#<...>} as strings @code{"#<...>"} so that the format output can always +be processed by @code{read}. +@refill +@item @code{~:A} +Print out readproof. Prints out internal objects represented as +@code{#<...>} as strings @code{"#<...>"} so that the format output can always +be processed by @code{read}. +@item @code{~Q} +Prints information and a copyright notice on the format implementation. +@table @asis +@item @code{~:Q} +prints format version. +@end table +@refill +@item @code{~F, ~E, ~G, ~$} +may also print number strings, i.e. passing a number as a string and +format it accordingly. +@end table + +@subsubsection Configuration Variables + +Format has some configuration variables at the beginning of +@file{format.scm} to suit the systems and users needs. There should be +no modification necessary for the configuration that comes with SLIB. +If modification is desired the variable should be set after the format +code is loaded. Format detects automatically if the running scheme +system implements floating point numbers and complex numbers. + +@table @asis + +@item @var{format:symbol-case-conv} +Symbols are converted by @code{symbol->string} so the case type of the +printed symbols is implementation dependent. +@code{format:symbol-case-conv} is a one arg closure which is either +@code{#f} (no conversion), @code{string-upcase}, @code{string-downcase} +or @code{string-capitalize}. (default @code{#f}) + +@item @var{format:iobj-case-conv} +As @var{format:symbol-case-conv} but applies for the representation of +implementation internal objects. (default @code{#f}) + +@item @var{format:expch} +The character prefixing the exponent value in @code{~E} printing. (default +@code{#\E}) + +@end table + +@subsubsection Compatibility With Other Format Implementations + +@table @asis +@item SLIB format 2.x: +See @file{format.doc}. + +@item SLIB format 1.4: +Downward compatible except for padding support and @code{~A}, @code{~S}, +@code{~P}, @code{~X} uppercase printing. SLIB format 1.4 uses C-style +@code{printf} padding support which is completely replaced by the CL +@code{format} padding style. + +@item MIT C-Scheme 7.1: +Downward compatible except for @code{~}, which is not documented +(ignores all characters inside the format string up to a newline +character). (7.1 implements @code{~a}, @code{~s}, +~@var{newline}, @code{~~}, @code{~%}, numerical and variable +parameters and @code{:/@@} modifiers in the CL sense).@refill + +@item Elk 1.5/2.0: +Downward compatible except for @code{~A} and @code{~S} which print in +uppercase. (Elk implements @code{~a}, @code{~s}, @code{~~}, and +@code{~%} (no directive parameters or modifiers)).@refill + +@item Scheme->C 01nov91: +Downward compatible except for an optional destination parameter: S2C +accepts a format call without a destination which returns a formatted +string. This is equivalent to a #f destination in S2C. (S2C implements +@code{~a}, @code{~s}, @code{~c}, @code{~%}, and @code{~~} (no directive +parameters or modifiers)).@refill + +@end table + +This implementation of format is solely useful in the SLIB context +because it requires other components provided by SLIB.@refill + + +@node Generic-Write, Line I/O, Format, Procedures +@section Generic-Write + +@code{(require 'generic-write)} + +@code{generic-write} is a procedure that transforms a Scheme data value +(or Scheme program expression) into its textual representation and +prints it. The interface to the procedure is sufficiently general to +easily implement other useful formatting procedures such as pretty +printing, output to a string and truncated output.@refill + +@deffn Procedure generic-write obj display? width output +@table @var +@item obj +Scheme data value to transform. +@item display? +Boolean, controls whether characters and strings are quoted. +@item width +Extended boolean, selects format: +@table @asis +@item #f +single line format +@item integer > 0 +pretty-print (value = max nb of chars per line) +@end table +@item output +Procedure of 1 argument of string type, called repeatedly with +successive substrings of the textual representation. This procedure can +return @code{#f} to stop the transformation. +@end table + +The value returned by @code{generic-write} is undefined. + +Examples: +@lisp +(write obj) @equiv{} (generic-write obj #f #f @var{display-string}) +(display obj) @equiv{} (generic-write obj #t #f @var{display-string}) +@end lisp +@noindent +where +@lisp +@var{display-string} @equiv{} +(lambda (s) (for-each write-char (string->list s)) #t) +@end lisp +@end deffn + + + + + +@node Line I/O, Multi-Processing, Generic-Write, Procedures +@section Line I/O + +@code{(require 'line-i/o)} + +@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 + + + + +@node Multi-Processing, Object-To-String, Line I/O, Procedures +@section Multi-Processing + +@code{(require 'process)} + +@deffn Procedure add-process! proc +Adds proc, which must be a procedure (or continuation) capable of +accepting accepting one argument, to the @code{process:queue}. The +value returned is unspecified. The argument to @var{proc} should be +ignored. If @var{proc} returns, the process is killed.@refill +@end deffn + +@deffn Procedure process:schedule! +Saves the current process on @code{process:queue} and runs the next +process from @code{process:queue}. The value returned is +unspecified.@refill +@end deffn + + +@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}). +@end deffn + + + + + +@node Object-To-String, Pretty-Print, Multi-Processing, Procedures +@section Object-To-String + +@code{(require 'object->string)} + +@defun object->string obj +Returns the textual representation of @var{obj} as a string. +@end defun + + + + +@node Pretty-Print, Sorting, Object-To-String, Procedures +@section Pretty-Print + +@code{(require 'pretty-print)} + +@deffn Procedure pretty-print obj +@deffnx Procedure pretty-print obj port + +@code{pretty-print}s @var{obj} on @var{port}. If @var{port} is not +specified, @code{current-output-port} is used. + +Example: +@example +@group +(pretty-print '((1 2 3 4 5) (6 7 8 9 10) (11 12 13 14 15) + (16 17 18 19 20) (21 22 23 24 25))) + @print{} ((1 2 3 4 5) + @print{} (6 7 8 9 10) + @print{} (11 12 13 14 15) + @print{} (16 17 18 19 20) + @print{} (21 22 23 24 25)) +@end group +@end example +@end deffn + + +@code{(require 'pprint-file)} + +@deffn Procedure pprint-file infile +@deffnx Procedure pprint-file infile outfile +Pretty-prints all the code in @var{infile}. If @var{outfile} is +specified, the output goes to @var{outfile}, otherwise it goes to +@code{(current-output-port)}.@refill +@end deffn + +@defun pprint-filter-file infile proc outfile +@defunx pprint-filter-file infile proc +@var{infile} is a port or a string naming an existing file. Scheme +source code expressions and definitions are read from the port (or file) +and @var{proc} is applied to them sequentially. + +@var{outfile} is a port or a string. If no @var{outfile} is specified +then @code{current-output-port} is assumed. These expanded expressions +are then @code{pretty-print}ed to this port. + +Whitepsace and comments (introduced by @code{;}) which are not part of +scheme expressions are reproduced in the output. This procedure does +not affect the values returned by @code{current-input-port} and +@code{current-output-port}.@refill +@end defun + +@code{pprint-filter-file} can be used to pre-compile macro-expansion and +thus can reduce loading time. The following will write into +@file{exp-code.scm} the result of expanding all defmacros in +@file{code.scm}. +@lisp +(require 'pprint-file) +(require 'defmacroexpand) +(defmacro:load "my-macros.scm") +(pprint-filter-file "code.scm" defmacro:expand* "exp-code.scm") +@end lisp + + +@node Sorting, Topological Sort, Pretty-Print, Procedures +@section Sorting + +@code{(require 'sort)} + +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. + +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,@refill + +@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 +comparison functions. Think of @code{(less? x y)} as saying when +@code{x} must @emph{not} precede @code{y}.@refill + +@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)}).@refill + +Returns @code{#f} when the sequence contains at least one out-of-order +pair. It is an error if the sequence is neither a list nor a vector. +@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.)@refill +@end deffn + +@defun sort sequence less? +Accepts either a list or a vector, 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.@refill +@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, the sorted elements are put back in the same +vector. + +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 <) +@end lisp +@end deffn + +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@refill +@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, Standard Formatted I/O, Sorting, Procedures +@section Topological Sort + +@code{(require 'topological-sort)} or @code{(require 'tsort)} + +@noindent +The algorithm is inspired by Cormen, Leiserson and Rivest (1990) +@cite{Introduction to Algorithms}, chapter 23. + +@defun tsort dag pred +@defunx topological-sort dag pred +where +@table @var +@item dag +is a list of sublists. The car of each sublist is a vertex. The cdr is +the adjacency list of that vertex, i.e. a list of all vertices to which +there exists an edge from the car vertex. +@item pred +is one of @code{eq?}, @code{eqv?}, @code{equal?}, @code{=}, +@code{char=?}, @code{char-ci=?}, @code{string=?}, or @code{string-ci=?}. +@end table + +Sort the directed acyclic graph @var{dag} so that for every edge from +vertex @var{u} to @var{v}, @var{u} will come before @var{v} in the +resulting list of vertices. + +Time complexity: O (|V| + |E|) + +Example (from Cormen): +@quotation +Prof. Bumstead topologically sorts his clothing when getting +dressed. The first argument to `tsort' describes which +garments he needs to put on before others. (For example, +Prof Bumstead needs to put on his shirt before he puts on his +tie or his belt.) `tsort' gives the correct order of dressing: +@end quotation + +@example +(require 'tsort) +(tsort '((shirt tie belt) + (tie jacket) + (belt jacket) + (watch) + (pants shoes belt) + (undershorts pants shoes) + (socks shoes)) + eq?) +@result{} +(socks undershorts pants shoes watch shirt belt tie jacket) +@end example +@end defun + +@node Standard Formatted I/O, String-Case, Topological Sort, Procedures +@section Standard Formatted I/O + +@menu +* Standard Formatted Output:: +* Standard Formatted Input:: +@end menu + +@subsection stdio + +@code{(require 'stdio)} + +@code{require}s @code{printf} and @code{scanf} and additionally defines +the symbols: + +@defvar stdin +Defined to be @code{(current-input-port)}. +@end defvar +@defvar stdout +Defined to be @code{(current-output-port)}. +@end defvar +@defvar stderr +Defined to be @code{(current-error-port)}. +@end defvar + + +@node Standard Formatted Output, Standard Formatted Input, Standard Formatted I/O, Standard Formatted I/O +@subsection Standard Formatted Output + +@code{(require 'printf)} + +@deffn Procedure printf format arg1 @dots{} +@deffnx Procedure fprintf port format arg1 @dots{} +@deffnx Procedure sprintf str format arg1 @dots{} + +Each function converts, formats, and outputs its @var{arg1} @dots{} +arguments according to the control string @var{format} argument and +returns the number of characters output. + +@code{printf} sends its output to the port @code{(current-output-port)}. +@code{fprintf} sends its output to the port @var{port}. @code{sprintf} +@code{string-set!}s locations of the non-constant string argument +@var{str} to the output characters. + +@quotation +@emph{Note:} sprintf should be changed to a macro so a @code{substring} +expression could be used for the @var{str} argument. +@end quotation + +The string @var{format} contains plain characters which are copied to +the output stream, and conversion specifications, each of which results +in fetching zero or more of the arguments @var{arg1} @dots{}. The +results are undefined if there are an insufficient number of arguments +for the format. If @var{format} is exhausted while some of the +@var{arg1} @dots{} arguments remain unused, the excess @var{arg1} +@dots{} arguments are ignored. + +The conversion specifications in a format string have the form: + +@example +% @r{[} @var{flags} @r{]} @r{[} @var{width} @r{]} @r{[} . @var{precision} @r{]} @r{[} @var{type} @r{]} @var{conversion} +@end example + +An output conversion specifications consist of an initial @samp{%} +character followed in sequence by: + +@itemize @bullet +@item +Zero or more @dfn{flag characters} that modify the normal behavior of +the conversion specification. + +@table @asis +@item @samp{-} +Left-justify the result in the field. Normally the result is +right-justified. + +@item @samp{+} +For the signed @samp{%d} and @samp{%i} conversions and all inexact +conversions, prefix a plus sign if the value is positive. + +@item @samp{ } +For the signed @samp{%d} and @samp{%i} conversions, if the result +doesn't start with a plus or minus sign, prefix it with a space +character instead. Since the @samp{+} flag ensures that the result +includes a sign, this flag is ignored if both are specified. + +@item @samp{#} +For inexact conversions, @samp{#} specifies that the result should +always include a decimal point, even if no digits follow it. For the +@samp{%g} and @samp{%G} conversions, this also forces trailing zeros +after the decimal point to be printed where they would otherwise be +elided. + +For the @samp{%o} conversion, force the leading digit to be @samp{0}, as +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}). + + +@item @samp{0} +Pad the field with zeros instead of spaces. The zeros are placed after +any indication of sign or base. This flag is ignored if the @samp{-} +flag is also specified, or if a precision is specified for an exact +converson. +@end table + +@item +An optional decimal integer specifying the @dfn{minimum field width}. +If the normal conversion produces fewer characters than this, the field +is padded (with spaces or zeros per the @samp{0} flag) to the specified +width. This is a @emph{minimum} width; if the normal conversion +produces more characters than this, the field is @emph{not} truncated. +@cindex minimum field width (@code{printf}) + +Alternatively, if the field width is @samp{*}, the next argument in the +argument list (before the actual value to be printed) is used as the +field width. The width value must be an integer. If the value is +negative it is as though the @samp{-} flag is set (see above) and the +absolute value is used as the field width. + +@item +An optional @dfn{precision} to specify the number of digits to be +written for numeric conversions and the maximum field width for string +conversions. The precision is specified by a period (@samp{.}) followed +optionally by a decimal integer (which defaults to zero if omitted). +@cindex precision (@code{printf}) + +Alternatively, if the precision is @samp{.*}, the next argument in the +argument list (before the actual value to be printed) is used as the +precision. The value must be an integer, and is ignored if negative. +If you specify @samp{*} for both the field width and precision, the +field width argument precedes the precision argument. The @samp{.*} +precision is an enhancement. C library versions may not accept this +syntax. + +For the @samp{%f}, @samp{%e}, and @samp{%E} conversions, the precision +specifies how many digits follow the decimal-point character. The +default precision is @code{6}. If the precision is explicitly @code{0}, +the decimal point character is suppressed. + +For the @samp{%g} and @samp{%G} conversions, the precision specifies how +many significant digits to print. Significant digits are the first +digit before the decimal point, and all the digits after it. If the +precision is @code{0} or not specified for @samp{%g} or @samp{%G}, it is +treated like a value of @code{1}. If the value being printed cannot be +expressed accurately in the specified number of digits, the value is +rounded to the nearest number that fits. + +For exact conversions, if a precision is supplied it specifies the +minimum number of digits to appear; leading zeros are produced if +necessary. If a precision is not supplied, the number is printed with +as many digits as necessary. Converting an exact @samp{0} with an +explicit precision of zero produces no characters. + +@item +An optional one of @samp{l}, @samp{h} or @samp{L}, which is ignored for +numeric conversions. It is an error to specify these modifiers for +non-numeric conversions. + +@item +A character that specifies the conversion to be applied. +@end itemize + +@subsubsection Exact Conversions + +@table @asis +@item @samp{d}, @samp{i} +Print an integer as a signed decimal number. @samp{%d} and @samp{%i} +are synonymous for output, but are different when used with @code{scanf} +for input (@pxref{Standard Formatted Input}). + +@item @samp{o} +Print an integer as an unsigned octal number. + +@item @samp{u} +Print an integer as an unsigned decimal number. + +@item @samp{x}, @samp{X} +Print an integer as an unsigned hexadecimal number. @samp{%x} prints +using the digits @samp{0123456789abcdef}. @samp{%X} prints using the +digits @samp{0123456789ABCDEF}. +@end table + +@subsubsection Inexact Conversions +@emph{Note:} Inexact conversions are not supported yet. + +@table @asis +@item @samp{f} +Print a floating-point number in fixed-point notation. + +@item @samp{e}, @samp{E} +Print a floating-point number in exponential notation. @samp{%e} prints +@samp{e} between mantissa and exponont. @samp{%E} prints @samp{E} +between mantissa and exponont. + +@item @samp{g}, @samp{G} +Print a floating-point number in either normal or exponential notation, +whichever is more appropriate for its magnitude. @samp{%g} prints +@samp{e} between mantissa and exponont. @samp{%G} prints @samp{E} +between mantissa and exponont. +@end table + +@subsubsection Other Conversions +@table @asis +@item @samp{c} +Print a single character. The @samp{-} flag is the only one which can +be specified. It is an error to specify a precision. + +@item @samp{s} +Print a string. The @samp{-} flag is the only one which can be +specified. A precision specifies the maximum number of characters to +output; otherwise all characters in the string are output. + +@item @samp{a}, @samp{A} +Print a scheme expression. The @samp{-} flag left-justifies the output. +The @samp{#} flag specifies that strings and characters should be quoted +as by @code{write} (which can be read using @code{read}); otherwise, +output is as @code{display} prints. A precision specifies the maximum +number of characters to output; otherwise as many characters as needed +are output. + +@emph{Note:} @samp{%a} and @samp{%A} are SLIB extensions. + +@c @item @samp{p} +@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 Note that this conversion specification never produces any output. + +@c @item @samp{m} +@c Print the string corresponding to the value of @code{errno}. +@c (This is a GNU extension.) +@c @xref{Other Output Conversions}. + +@item @samp{%} +Print a literal @samp{%} character. No argument is consumed. It is an +error to specifiy flags, field width, precision, or type modifiers with +@samp{%%}. +@end table +@end deffn + + +@node Standard Formatted Input, , Standard Formatted Output, Standard Formatted I/O +@subsection Standard Formatted Input + +@code{(require 'scanf)} + +@deffn Function scanf-read-list format +@deffnx Function scanf-read-list format port +@deffnx Function scanf-read-list format string +@end deffn + +@defmac scanf format arg1 @dots{} +@defmacx fscanf port format arg1 @dots{} +@defmacx sscanf str format arg1 @dots{} + +Each function reads characters, interpreting them according to the +control string @var{format} argument. + +@code{scanf-read-list} returns a list of the items specified as far as +the input matches @var{format}. @code{scanf}, @code{fscanf}, and +@code{sscanf} return the number of items successfully matched and +stored. @code{scanf}, @code{fscanf}, and @code{sscanf} also set the +location corresponding to @var{arg1} @dots{} using the methods: + +@table @asis +@item symbol +@code{set!} +@item car expression +@code{set-car!} +@item cdr expression +@code{set-cdr!} +@item vector-ref expression +@code{vector-set!} +@item substring expression +@code{substring-move-left!} +@end table + +The argument to a @code{substring} expression in @var{arg1} @dots{} must +be a non-constant string. Characters will be stored starting at the +position specified by the second argument to @code{substring}. The +number of characters stored will be limited by either the position +specified by the third argument to @code{substring} or the length of the +matched string, whichever is less. + +The control string, @var{format}, contains conversion specifications and +other characters used to direct interpretation of input sequences. The +control string contains: + +@itemize @bullet +@item White-space characters (blanks, tabs, newlines, or formfeeds) +that cause input to be read (and discarded) up to the next +non-white-space character. + +@item An ordinary character (not @samp{%}) that must match the next +character of the input stream. + +@item Conversion specifications, consisting of the character @samp{%}, an +optional assignment suppressing character @samp{*}, an optional +numerical maximum-field width, an optional @samp{l}, @samp{h} or +@samp{L} which is ignored, and a conversion code. + +@c @item The conversion specification can alternatively be prefixed by +@c the character sequence @samp{%n$} instead of the character @samp{%}, +@c where @var{n} is a decimal integer in the range. The @samp{%n$} +@c construction indicates that the value of the next input field should be +@c placed in the @var{n}th place in the return list, rather than to the next +@c unused one. The two forms of introducing a conversion specification, +@c @samp{%} and @samp{%n$}, must not be mixed within a single format string +@c with the following exception: Skip fields (see below) can be designated +@c as @samp{%*} or @samp{%n$*}. In the latter case, @var{n} is ignored. + +@end itemize + +Unless the specification contains the @samp{n} conversion character +(described below), a conversion specification directs the conversion of +the next input field. The result of a conversion specification is +returned in the position of the corresponding argument points, unless +@samp{*} indicates assignment suppression. Assignment suppression +provides a way to describe an input field to be skipped. An input field +is defined as a string of characters; it extends to the next +inappropriate character or until the field width, if specified, is +exhausted. + +@quotation +@emph{Note:} This specification of format strings differs from the +@cite{ANSI C} and @cite{POSIX} specifications. In SLIB, white space +before an input field is not skipped unless white space appears before +the conversion specification in the format string. In order to write +format strings which work identically with @cite{ANSI C} and SLIB, +prepend whitespace to all conversion specifications except @samp{[} and +@samp{c}. +@end quotation + +The conversion code indicates the interpretation of the input field; For +a suppressed field, no value is returned. The following conversion +codes are legal: + +@table @asis + +@item @samp{%} +A single % is expected in the input at this point; no value is returned. + +@item @samp{d}, @samp{D} +A decimal integer is expected. + +@item @samp{u}, @samp{U} +An unsigned decimal integer is expected. + +@item @samp{o}, @samp{O} +An octal integer is expected. + +@item @samp{x}, @samp{X} +A hexadecimal integer is expected. + +@item @samp{i} +An integer is expected. Returns the value of the next input item, +interpreted according to C conventions; a leading @samp{0} implies +octal, a leading @samp{0x} implies hexadecimal; otherwise, decimal is +assumed. + +@item @samp{n} +Returns the total number of bytes (including white space) read by +@code{scanf}. No input is consumed by @code{%n}. + +@item @samp{f}, @samp{F}, @samp{e}, @samp{E}, @samp{g}, @samp{G} +A floating-point number is expected. The input format for +floating-point numbers is an optionally signed string of digits, +possibly containing a radix character @samp{.}, followed by an optional +exponent field consisting of an @samp{E} or an @samp{e}, followed by an +optional @samp{+}, @samp{-}, or space, followed by an integer. + +@item @samp{c}, @samp{C} +@var{Width} characters are expected. The normal skip-over-white-space +is suppressed in this case; to read the next non-space character, use +@samp{%1s}. If a field width is given, a string is returned; up to the +indicated number of characters is read. + +@item @samp{s}, @samp{S} +A character string is expected The input field is terminated by a +white-space character. @code{scanf} cannot read a null string. + +@item @samp{[} +Indicates string data and the normal skip-over-leading-white-space is +suppressed. The left bracket is followed by a set of characters, called +the scanset, and a right bracket; the input field is the maximal +sequence of input characters consisting entirely of characters in the +scanset. @samp{^}, when it appears as the first character in the +scanset, serves as a complement operator and redefines the scanset as +the set of all characters not contained in the remainder of the scanset +string. Construction of the scanset follows certain conventions. A +range of characters may be represented by the construct first-last, +enabling @samp{[0123456789]} to be expressed @samp{[0-9]}. Using this +convention, first must be lexically less than or equal to last; +otherwise, the dash stands for itself. The dash also stands for itself +when it is the first or the last character in the scanset. To include +the right square bracket as an element of the scanset, it must appear as +the first character (possibly preceded by a @samp{^}) of the scanset, in +which case it will not be interpreted syntactically as the closing +bracket. At least one character must match for this conversion to +succeed. +@end table + +The @code{scanf} functions terminate their conversions at end-of-file, +at the end of the control string, or when an input character conflicts +with the control string. In the latter case, the offending character is +left unread in the input stream. +@end defmac + +@node String-Case, String Ports, Standard Formatted I/O, Procedures +@section String-Case + +@code{(require 'string-case)} + +@deffn Procedure string-upcase str +@deffnx Procedure string-downcase str +@deffnx Procedure string-capitalize str +The obvious string conversion routines. These are non-destructive. +@end deffn + +@defun string-upcase! str +@defunx string-downcase! str +@defunx string-captialize! str +The destructive versions of the functions above. +@end defun + + + + + +@node String Ports, String Search, String-Case, Procedures +@section String Ports + +@code{(require 'string-port)} + +@deffn Procedure call-with-output-string proc +@var{proc} must be a procedure of one argument. This procedure calls +@var{proc} with one argument: a (newly created) output port. When the +function returns, the string composed of the characters written into the +port is returned.@refill +@end deffn + +@deffn Procedure call-with-input-string string proc +@var{proc} must be a procedure of one argument. This procedure calls +@var{proc} with one argument: an (newly created) input port from which +@var{string}'s contents may be read. When @var{proc} returns, the port +is closed and the value yielded by the procedure @var{proc} is +returned.@refill +@end deffn + + +@node String Search, Tektronix Graphics Support, String Ports, Procedures +@section String Search + +@code{(require 'string-search)} + +@deffn Procedure string-index string char +Returns the index of the first occurence of @var{char} within +@var{string}, or @code{#f} if the @var{string} does not contain a +character @var{char}. +@end deffn + +@deffn procedure substring? pattern string +Searches @var{string} to see if some substring of @var{string} is equal +to @var{pattern}. @code{substring?} returns the index of the first +character of the first substring of @var{string} that is equal to +@var{pattern}; or @code{#f} if @var{string} does not contain +@var{pattern}. + +@example +(substring? "rat" "pirate") @result{} 2 +(substring? "rat" "outrage") @result{} #f +(substring? "" any-string) @result{} 0 +@end example +@end deffn + +@deffn Procedure find-string-from-port? str in-port max-no-chars +@deffnx Procedure find-string-from-port? str in-port +Looks for a string @var{str} within the first @var{max-no-chars} chars +of the input port @var{in-port}. @var{max-no-chars} may be omitted: in +that case, the search span is limited by the end of the input stream. +When the @var{str} is found, the function returns the number of +characters it has read from the port, and the port is set to read the +first char after that (that is, after the @var{str}) The function +returns @code{#f} when the @var{str} isn't found. + +@code{find-string-from-port?} reads the port @emph{strictly} +sequentially, and does not perform any buffering. So +@code{find-string-from-port?} can be used even if the @var{in-port} is +open to a pipe or other communication channel. +@end deffn + + +@node Tektronix Graphics Support, Tree Operations, String Search, Procedures +@section Tektronix Graphics Support + +@emph{Note:} The Tektronix graphics support files need more work, and +are not complete. + +@subsection Tektronix 4000 Series Graphics + +The Tektronix 4000 series graphics protocol gives the user a 1024 by +1024 square drawing area. The origin is in the lower left corner of the +screen. Increasing y is up and increasing x is to the right. + +The graphics control codes are sent over the current-output-port and can +be mixed with regular text and ANSI or other terminal control sequences. + +@deffn Procedure tek40:init +@end deffn + +@deffn Procedure tek40:graphics +@end deffn + +@deffn Procedure tek40:text +@end deffn + +@deffn Procedure tek40:linetype linetype +@end deffn + +@deffn Procedure tek40:move x y +@end deffn + +@deffn Procedure tek40:draw x y +@end deffn + +@deffn Procedure tek40:put-text x y str +@end deffn + +@deffn Procedure tek40:reset +@end deffn + + +@subsection Tektronix 4100 Series Graphics + +The graphics control codes are sent over the current-output-port and can +be mixed with regular text and ANSI or other terminal control sequences. + +@deffn Procedure tek41:init +@end deffn + +@deffn Procedure tek41:reset +@end deffn + +@deffn Procedure tek41:graphics +@end deffn + +@deffn Procedure tek41:move x y +@end deffn + +@deffn Procedure tek41:draw x y +@end deffn + +@deffn Procedure tek41:point x y number +@end deffn + +@deffn Procedure tek41:encode-x-y x y +@end deffn + +@deffn Procedure tek41:encode-int number +@end deffn + + + +@node Tree Operations, , Tektronix Graphics Support, Procedures +@section Tree operations + +@code{(require 'tree)} + +These are operations that treat lists a representations of trees. + +@defun subst new old tree +@defunx substq new old tree +@defunx substv new old tree +@code{subst} makes a copy of @var{tree}, substituting @var{new} for +every subtree or leaf of @var{tree} which is @code{equal?} to @var{old} +and returns a modified tree. The original @var{tree} is unchanged, but +may share parts with the result.@refill + +@code{substq} and @code{substv} are similar, but test against @var{old} +using @code{eq?} and @code{eqv?} respectively.@refill + +Examples: +@lisp +(substq 'tempest 'hurricane '(shakespeare wrote (the hurricane))) + @result{} (shakespeare wrote (the tempest)) +(substq 'foo '() '(shakespeare wrote (twelfth night))) + @result{} (shakespeare wrote (twelfth night . foo) . foo) +(subst '(a . cons) '(old . pair) + '((old . spice) ((old . shoes) old . pair) (old . pair))) + @result{} ((old . spice) ((old . shoes) a . cons) (a . cons)) +@end lisp +@end defun + +@defun copy-tree tree +Makes a copy of the nested list structure @var{tree} using new pairs and +returns it. All levels are copied, so that none of the pairs in the +tree are @code{eq?} to the original ones -- only the leaves are.@refill + +Example: +@lisp +(define bar '(bar)) +(copy-tree (list bar 'foo)) + @result{} ((bar) foo) +(eq? bar (car (copy-tree (list bar 'foo)))) + @result{} #f +@end lisp +@end defun + + + + + +@node Standards Support, Session Support, Procedures, Top +@chapter Standards Support + + + +@menu +* With-File:: 'with-file +* Transcripts:: 'transcript +* Rev2 Procedures:: 'rev2-procedures +* Rev4 Optional Procedures:: 'rev4-optional-procedures +* Multi-argument / and -:: 'multiarg/and- +* Multi-argument Apply:: 'multiarg-apply +* Rationalize:: 'rationalize +* Promises:: 'promise +* Dynamic-Wind:: 'dynamic-wind +* Values:: 'values +* Time:: 'time +* CLTime:: 'common-lisp-time +@end menu + +@node With-File, Transcripts, Standards Support, Standards Support +@section With-File + +@code{(require 'with-file)} + +@defun with-input-from-file file thunk +@defunx with-output-to-file file thunk +Description found in R4RS. +@end defun + +@node Transcripts, Rev2 Procedures, With-File, Standards Support +@section Transcripts + +@code{(require 'transcript)} + +@defun transcript-on filename +@defunx transcript-off filename +Redefines @code{read-char}, @code{read}, @code{write-char}, +@code{write}, @code{display}, and @code{newline}.@refill +@end defun + + + + + +@node Rev2 Procedures, Rev4 Optional Procedures, Transcripts, Standards Support +@section Rev2 Procedures + +@code{(require 'rev2-procedures)} + +The procedures below were specified in the @cite{Revised^2 Report on +Scheme}. @strong{N.B.}: The symbols @code{1+} and @code{-1+} are not +@cite{R4RS} syntax. Scheme->C, for instance, barfs on this +module.@refill + +@deffn Procedure substring-move-left! string1 start1 end1 string2 start2 +@deffnx Procedure substring-move-right! string1 start1 end1 string2 start2 +@var{string1} and @var{string2} must be a strings, and @var{start1}, +@var{start2} and @var{end1} must be exact integers satisfying@refill + +@display +0 <= @var{start1} <= @var{end1} <= (string-length @var{string1}) +0 <= @var{start2} <= @var{end1} - @var{start1} + @var{start2} <= (string-length @var{string2}) +@end display + +@code{substring-move-left!} and @code{substring-move-right!} store +characters of @var{string1} beginning with index @var{start1} +(inclusive) and ending with index @var{end1} (exclusive) into +@var{string2} beginning with index @var{start2} (inclusive).@refill + +@code{substring-move-left!} stores characters in time order of +increasing indices. @code{substring-move-right!} stores characters in +time order of increasing indeces.@refill +@end deffn + +@deffn Procedure substring-fill! string start end char +Fills the elements @var{start}--@var{end} of @var{string} with the +character @var{char}.@refill +@end deffn + +@defun string-null? str +@equiv{} @code{(= 0 (string-length @var{str}))} +@end defun + +@deffn Procedure append! . pairs +Destructively appends its arguments. Equivalent to @code{nconc}. +@end deffn + +@defun 1+ n +Adds 1 to @var{n}. +@end defun + +@defun -1+ n +Subtracts 1 from @var{n}. +@end defun + +@defun <? +@defunx <=? +@defunx =? +@defunx >? +@defunx >=? +These are equivalent to the procedures of the same name but without the +trailing @samp{?}. +@end defun + + + +@node Rev4 Optional Procedures, Multi-argument / and -, Rev2 Procedures, Standards Support +@section Rev4 Optional Procedures + +@code{(require 'rev4-optional-procedures)} + +For the specification of these optional procedures, +@xref{Standard procedures, , ,r4rs, Revised(4) Scheme}. + +@defun list-tail l p +@end defun + +@defun string->list s +@end defun + +@defun list->string l +@end defun + +@defun string-copy +@end defun + +@deffn Procedure string-fill! s obj +@end deffn + +@defun list->vector l +@end defun + +@defun vector->list s +@end defun + +@deffn Procedure vector-fill! s obj +@end deffn + + + + + +@node Multi-argument / and -, Multi-argument Apply, Rev4 Optional Procedures, Standards Support +@section Multi-argument / and - + +@code{(require 'mutliarg/and-)} + +For the specification of these optional forms, @xref{Numerical +operations, , ,r4rs, Revised(4) Scheme}. The @code{two-arg:}* forms are +only defined if the implementation does not support the many-argument +forms.@refill + +@defun two-arg:/ n1 n2 +The original two-argument version of @code{/}. +@end defun + +@defun / divident . divisors +@end defun + +@defun two-arg:- n1 n2 +The original two-argument version of @code{-}. +@end defun + +@defun - minuend . subtrahends +@end defun + + + + + +@node Multi-argument Apply, Rationalize, Multi-argument / and -, Standards Support +@section Multi-argument Apply + +@code{(require 'multiarg-apply)} + +@noindent +For the specification of this optional form, +@xref{Control features, , ,r4rs, Revised(4) Scheme}. + +@defun two-arg:apply proc l +The implementation's native @code{apply}. Only defined for +implementations which don't support the many-argument version. +@end defun + +@defun apply proc . args +@end defun + + + + + +@node Rationalize, Promises, Multi-argument Apply, Standards Support +@section Rationalize + +@code{(require 'rationalize)} + +The procedure rationalize is interesting because most programming +languages do not provide anything analogous to it. For simplicity, we +present an algorithm which computes the correct result for exact +arguments (provided the implementation supports exact rational numbers +of unlimited precision), and produces a reasonable answer for inexact +arguments when inexact arithmetic is implemented using floating-point. +We thank Alan Bawden for contributing this algorithm. + +@defun rationalize x e +@end defun + + + + + +@node Promises, Dynamic-Wind, Rationalize, Standards Support +@section Promises + +@code{(require 'promise)} + +@defun make-promise proc +@end defun + +Change occurrences of @code{(delay @var{expression})} to +@code{(make-promise (lambda () @var{expression}))} and @code{(define +force promise:force)} to implement promises if your implementation +doesn't support them +(@pxref{Control features, , ,r4rs, Revised(4) Scheme}). + + + + +@node Dynamic-Wind, Values, Promises, Standards Support +@section Dynamic-Wind + +@code{(require 'dynamic-wind)} + +This facility is a generalization of Common LISP @code{unwind-protect}, +designed to take into account the fact that continuations produced by +@code{call-with-current-continuation} may be reentered.@refill + +@deffn Procedure dynamic-wind thunk1 thunk2 thunk3 +The arguments @var{thunk1}, @var{thunk2}, and @var{thunk3} must all be +procedures of no arguments (thunks).@refill + +@code{dynamic-wind} calls @var{thunk1}, @var{thunk2}, and then +@var{thunk3}. The value returned by @var{thunk2} is returned as the +result of @code{dynamic-wind}. @var{thunk3} is also called just before +control leaves the dynamic context of @var{thunk2} by calling a +continuation created outside that context. Furthermore, @var{thunk1} is +called before reentering the dynamic context of @var{thunk2} by calling +a continuation created inside that context. (Control is inside the +context of @var{thunk2} if @var{thunk2} is on the current return stack). + +@strong{Warning:} There is no provision for dealing with errors or +interrupts. If an error or interrupt occurs while using +@code{dynamic-wind}, the dynamic environment will be that in effect at +the time of the error or interrupt.@refill +@end deffn + + + + +@node Values, Time, Dynamic-Wind, Standards Support +@section Values + +@code{(require 'values)} + +@defun values obj @dots{} +@code{values} takes any number of arguments, and passes (returns) them +to its continuation.@refill +@end defun + + +@defun call-with-values thunk proc +@var{thunk} must be a procedure of no arguments, and @var{proc} must be +a procedure. @code{call-with-values} calls @var{thunk} with a +continuation that, when passed some values, calls @var{proc} with those +values as arguments.@refill + +Except for continuations created by the @code{call-with-values} +procedure, all continuations take exactly one value, as now; the effect +of passing no value or more than one value to continuations that were +not created by the @code{call-with-values} procedure is +unspecified.@refill +@end defun + +@node Time, CLTime, Values, Standards Support +@section Time + +The procedures @code{current-time}, @code{difftime}, and +@code{offset-time} are supported by all implementations (SLIB provides +them if feature @code{('current-time)} is missing. @code{current-time} +returns a @dfn{calendar time} (caltime) which can be a number or other +type. + +@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{CLTime}. On implementations +which cannot support actual times, @code{current-time} will increment a +counter and return its value when called. +@end defun + +@defun difftime caltime1 caltime0 +Returns the difference (number of seconds) between twe calendar times: +@var{caltime1} - @var{caltime0}. @var{caltime0} can 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 + +@example +(require 'posix-time) +@end example + +These procedures are intended to be compatible with Posix time +conversion functions. + +@defvar *timezone* +contains the difference, in seconds, between UTC 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 + +@defun tzset +initializes the @var{*timezone*} variable from the TZ environment +variable. This function is automatically called by the other time +conversion functions that depend on the time zone. +@end defun + +@defun gmtime caltime +converts the calendar time @var{caltime} to a vector of integers +representing the time expressed as Coordinated Universal Time (UTC). + +@defunx localtime caltime +converts the calendar time @var{caltime} to a vector of integers expressed +relative to the user's time zone. @code{localtime} sets the variable +@var{*timezone*} with the difference between Coordinated Universal Time +(UTC) and local standard time in seconds by calling @code{tzset}. +The elements of the returned vector are as follows: + +@enumerate 0 +@item + seconds (0 - 61) +@item + minutes (0 - 59) +@item + hours since midnight +@item + day of month +@item + month (0 - 11). Note difference from @code{decode-universal-time}. +@item + year (A.D.) +@item + day of week (0 - 6) +@item + day of year (0 - 365) +@item + 1 for daylight savings, 0 for regular time +@end enumerate +@end defun + +@defun mktime univtime +Converts a vector of integers in Coordinated Universal Time (UTC) format +to calendar time (caltime) format. +@end defun + +@defun asctime univtime +Converts the vector of integers @var{caltime} in Coordinated +Universal Time (UTC) format into a string of the form +@code{"Wed Jun 30 21:49:08 1993"}. +@end defun + +@defun ctime caltime +Equivalent to @code{(time:asctime (time:localtime @var{caltime}))}. +@end defun + +@node CLTime, , Time, Standards Support +@section CLTime + +@defun get-decoded-time +Equivalent to @code{(decode-universal-time (get-universal-time))}. +@end defun + +@defun get-universal-time +Returns the current time as @dfn{Universal Time}, number of seconds +since 00:00:00 Jan 1, 1900 GMT. Note that the reference time is +different from @code{current-time}. +@end defun + +@defun decode-universal-time univtime +Converts @var{univtime} to @dfn{Decoded Time} format. +Nine values are returned: +@enumerate 0 +@item + seconds (0 - 61) +@item + minutes (0 - 59) +@item + hours since midnight +@item + day of month +@item + month (1 - 12). Note difference from @code{gmtime} and @code{localtime}. +@item + year (A.D.) +@item + day of week (0 - 6) +@item + #t for daylight savings, #f otherwise +@item + hours west of GMT (-24 - +24) +@end enumerate + +Notice that the values returned by @code{decode-universal-time} do not +match the arguments to @code{encode-universal-time}. +@end defun + +@defun encode-universal-time second minute hour date month year +@defunx encode-universal-time second minute hour date month year time-zone +Converts the arguments in Decoded Time format to Universal Time format. +If @var{time-zone} is not specified, the returned time is adjusted for +daylight saving time. Otherwise, no adjustment is performed. + +Notice that the values returned by @code{decode-universal-time} do not +match the arguments to @code{encode-universal-time}. +@end defun + + +@node Session Support, Optional SLIB Packages, Standards Support, Top +@chapter Session Support + +@menu +* Repl:: Macros at top-level +* Quick Print:: Loop-safe Output +* Debug:: To err is human ... +* Breakpoints:: Pause execution +* Trace:: 'trace +* Getopt:: Command Line option parsing +* Command Line:: A command line reader for Scheme shells +* System Interface:: 'system and 'getenv + +Certain features are so simple, system-dependent, or widely subcribed +that they are supported by all implementations as part of the +@samp{*.init} files. + +The features described in the following sections are provided by all +implementations. + +* Require:: Module Management +* Vicinity:: Pathname Management +* Configuration:: Characteristics of Scheme Implementation +* Input/Output:: Things not provided by the Scheme specs. +* Legacy:: +* System:: LOADing, EVALing, ERRORing, and EXITing +@end menu + + + +@node Repl, Quick Print, Session Support, Session Support +@section Repl + +@code{(require 'repl)} + +Here is a read-eval-print-loop which, given an eval, evaluates forms. + +@deffn Procedure repl:top-level repl:eval +@code{read}s, @code{repl:eval}s and @code{write}s expressions from +@code{(current-input-port)} to @code{(current-output-port)} until an +end-of-file is encountered. @code{load}, @code{slib:eval}, +@code{slib:error}, and @code{repl:quit} dynamically bound during +@code{repl:top-level}.@refill +@end deffn + +@deffn Procedure repl:quit +Exits from the invocation of @code{repl:top-level}. +@end deffn + +The @code{repl:} procedures establish, as much as is possible to do +portably, a top level environment supporting macros. +@code{repl:top-level} uses @code{dynamic-wind} to catch error conditions +and interrupts. If your implementation supports this you are all set. + +Otherwise, if there is some way your implementation can catch error +conditions and interrupts, then have them call @code{slib:error}. It +will display its arguments and reenter @code{repl:top-level}. +@code{slib:error} dynamically bound by @code{repl:top-level}.@refill + +To have your top level loop always use macros, add any interrupt +catching lines and the following lines to your Scheme init file: +@lisp +(require 'macro) +(require 'repl) +(repl:top-level macro:eval) +@end lisp + +@node Quick Print, Debug, Repl, Session Support +@section Quick Print + +@code{(require 'qp)} + +@noindent +When displaying error messages and warnings, it is paramount that the +output generated for circular lists and large data structures be +limited. This section supplies a procedure to do this. It could be +much improved. + +@quotation +Notice that the neccessity for truncating output eliminates +Common-Lisp's @xref{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 + +@deffn Procedure qp arg1 @dots{} +@deffnx Procedure qpn arg1 @dots{} +@deffnx Procedure qpr arg1 @dots{} +@code{qp} writes its arguments, separated by spaces, to +@code{(current-output-port)}. @code{qp} compresses printing by +substituting @samp{...} for substructure it does not have sufficient +room to print. @code{qpn} is like @code{qp} but outputs a newline +before returning. @code{qpr} is like @code{qpn} except that it returns +its last argument.@refill +@end deffn + +@defvar *qp-width* +@code{*qp-width*} is the largest number of characters that @code{qp} +should use.@refill +@end defvar + +@node Debug, Breakpoints, Quick Print, Session Support +@section Debug + +@code{(require 'debug)} + +@noindent +Requiring @code{debug} automatically requires @code{trace} and +@code{break}. + +@noindent +An application with its own datatypes may want to substitute its own +printer for @code{qp}. This example shows how to do this: + +@example +(define qpn (lambda args) @dots{}) +(provide 'qp) +(require 'debug) +@end example + +@deffn Procedure trace-all file +Traces (@pxref{Trace}) all procedures @code{define}d at top-level in +file @file{file}. +@end deffn + +@deffn Procedure break-all file +Breakpoints (@pxref{Breakpoints}) all procedures @code{define}d at +top-level in file @file{file}. +@end deffn + +@node Breakpoints, Trace, Debug, Session Support +@section Breakpoints + +@code{(require 'break)} + +@defun init-debug +If your Scheme implementation does not support @code{break} or +@code{abort}, a message will appear when you @code{(require 'break)} or +@code{(require 'debug)} telling you to type @code{(init-debug)}. This +is in order to establish a top-level continuation. Typing +@code{(init-debug)} at top level sets up a continuation for +@code{break}. +@end defun + +@defun breakpoint arg1 @dots{} +Returns from the top level continuation and pushes the continuation from +which it was called on a continuation stack. +@end defun + +@defun continue +Pops the topmost continuation off of the continuation stack and returns +an unspecified value to it. +@defunx continue arg1 @dots{} +Pops the topmost continuation off of the continuation stack and returns +@var{arg1} @dots{} to it. +@end defun + +@defmac break proc1 @dots{} +Redefines the top-level named procedures given as arguments so that +@code{breakpoint} is called before calling @var{proc1} @dots{}. +@defmacx break +With no arguments, makes sure that all the currently broken identifiers +are broken (even if those identifiers have been redefined) and returns a +list of the broken identifiers. +@end defmac + +@defmac unbreak proc1 @dots{} +Turns breakpoints off for its arguments. +@defmacx unbreak +With no arguments, unbreaks all currently broken identifiers and returns +a list of these formerly broken identifiers. +@end defmac + +The following routines are the procedures which actually do the tracing +when this module is supplied by SLIB, rather than natively. If +defmacros are not natively supported by your implementation, these might +be more convenient to use. + +@defun breakf proc +@defunx breakf proc name +@defunx debug:breakf proc +@defunx debug:breakf proc name +To break, type +@lisp +(set! @var{symbol} (breakf @var{symbol})) +@end lisp +@noindent +or +@lisp +(set! @var{symbol} (breakf @var{symbol} '@var{symbol})) +@end lisp +@noindent +or +@lisp +(define @var{symbol} (breakf @var{function})) +@end lisp +@noindent +or +@lisp +(define @var{symbol} (breakf @var{function} '@var{symbol})) +@end lisp +@end defun + +@defun unbreakf proc +@defunx debug:unbreakf proc +To unbreak, type +@lisp +(set! @var{symbol} (unbreakf @var{symbol})) +@end lisp +@end defun + +@node Trace, Getopt, Breakpoints, Session Support +@section Tracing + +@code{(require 'trace)} + +@defmac trace proc1 @dots{} +Traces the top-level named procedures given as arguments. +@defmacx trace +With no arguments, makes sure that all the currently traced identifiers +are traced (even if those identifiers have been redefined) and returns a +list of the traced identifiers. +@end defmac + +@defmac untrace proc1 @dots{} +Turns tracing off for its arguments. +@defmacx untrace +With no arguments, untraces all currently traced identifiers and returns +a list of these formerly traced identifiers. +@end defmac + +The following routines are the procedures which actually do the tracing +when this module is supplied by SLIB, rather than natively. If +defmacros are not natively supported by your implementation, these might +be more convenient to use. + +@defun tracef proc +@defunx tracef proc name +@defunx debug:tracef proc +@defunx debug:tracef proc name +To trace, type +@lisp +(set! @var{symbol} (tracef @var{symbol})) +@end lisp +@noindent +or +@lisp +(set! @var{symbol} (tracef @var{symbol} '@var{symbol})) +@end lisp +@noindent +or +@lisp +(define @var{symbol} (tracef @var{function})) +@end lisp +@noindent +or +@lisp +(define @var{symbol} (tracef @var{function} '@var{symbol})) +@end lisp +@end defun + +@defun untracef proc +@defunx debug:untracef proc +To untrace, type +@lisp +(set! @var{symbol} (untracef @var{symbol})) +@end lisp +@end defun + + +@node Getopt, Command Line, Trace, Session Support +@section Getopt + +@code{(require 'getopt)} + +This routine implements Posix command line argument parsing. Notice +that returning values through global variables means that @code{getopt} +is @emph{not} reentrant. + +@defvar *optind* +Is the index of the current element of the command line. It is +initially one. In order to parse a new command line or reparse an old +one, @var{*opting*} must be reset. +@end defvar + +@defvar *optarg* +Is set by getopt to the (string) option-argument of the current option. +@end defvar + +@deffn Procedure getopt argc argv optstring +Returns the next option letter in @var{argv} (starting from +@code{(vector-ref argv *optind*)}) that matches a letter in +@var{optstring}. @var{argv} is a vector or list of strings, the 0th of +which getopt usually ignores. @var{argc} is the argument count, usually +the length of @var{argv}. @var{optstring} is a string of recognized +option characters; if a character is followed by a colon, the option +takes an argument which may be immediately following it in the string or +in the next element of @var{argv}. + +@var{*optind*} is the index of the next element of the @var{argv} vector +to be processed. It is initialized to 1 by @file{getopt.scm}, and +@code{getopt} updates it when it finishes with each element of +@var{argv}. + +@code{getopt} returns the next option character from @var{argv} that +matches a character in @var{optstring}, if there is one that matches. +If the option takes an argument, @code{getopt} sets the variable +@var{*optarg*} to the option-argument as follows: + +@itemize @bullet +@item +If the option was the last character in the string pointed to by an +element of @var{argv}, then @var{*optarg*} contains the next element of +@var{argv}, and @var{*optind*} is incremented by 2. If the resulting +value of @var{*optind*} is greater than or equal to @var{argc}, this +indicates a missing option argument, and @code{getopt} returns an error +indication. + +@item +Otherwise, @var{*optarg*} is set to the string following the option +character in that element of @var{argv}, and @var{*optind*} is +incremented by 1. +@end itemize + +If, when @code{getopt} is called, the string @code{(vector-ref argv +*optind*)} either does not begin with the character @code{#\-} or is +just @code{"-"}, @code{getopt} returns @code{#f} without changing +@var{*optind*}. If @code{(vector-ref argv *optind*)} is the string +@code{"--"}, @code{getopt} returns @code{#f} after incrementing +@var{*optind*}. + +If @code{getopt} encounters an option character that is not contained in +@var{optstring}, it returns the question-mark @code{#\?} character. If +it detects a missing option argument, it returns the colon character +@code{#\:} if the first character of @var{optstring} was a colon, or a +question-mark character otherwise. In either case, @code{getopt} sets +the variable @var{getopt:opt} to the option character that caused the +error. + +The special option @code{"--"} can be used to delimit the end of the +options; @code{#f} is returned, and @code{"--"} is skipped. + +RETURN VALUE + +@code{getopt} returns the next option character specified on the command +line. A colon @code{#\:} is returned if @code{getopt} detects a missing argument +and the first character of @var{optstring} was a colon @code{#\:}. + +A question-mark @code{#\?} is returned if @code{getopt} encounters an option +character not in @var{optstring} or detects a missing argument and the first +character of @var{optstring} was not a colon @code{#\:}. + +Otherwise, @code{getopt} returns @code{#f} when all command line options have been +parsed. + +Example: +@lisp +#! /usr/local/bin/scm +;;;This code is SCM specific. +(define argv (program-arguments)) +(require 'getopt) + +(define opts ":a:b:cd") +(let loop ((opt (getopt (length argv) argv opts))) + (case opt + ((#\a) (print "option a: " *optarg*)) + ((#\b) (print "option b: " *optarg*)) + ((#\c) (print "option c")) + ((#\d) (print "option d")) + ((#\?) (print "error" getopt:opt)) + ((#\:) (print "missing arg" getopt:opt)) + ((#f) (if (< *optind* (length argv)) + (print "argv[" *optind* "]=" + (list-ref argv *optind*))) + (set! *optind* (+ *optind* 1)))) + (if (< *optind* (length argv)) + (loop (getopt (length argv) argv opts)))) + +(slib:exit) +@end lisp +@end deffn + +@section Getopt-- + +@defun getopt-- argc argv optstring +The procedure @code{getopt--} is an extended version of @code{getopt} +which parses @dfn{long option names} of the form +@samp{--hold-the-onions} and @samp{--verbosity-level=extreme}. +@w{@code{Getopt--}} behaves as @code{getopt} except for non-empty +options beginning with @samp{--}. + +Options beginning with @samp{--} are returned as strings rather than +characters. If a value is assigned (using @samp{=}) to a long option, +@code{*optarg*} is set to the value. The @samp{=} and value are +not returned as part of the option string. + +No information is passed to @code{getopt--} concerning which long +options should be accepted or whether such options can take arguments. +If a long option did not have an argument, @code{*optarg} will be set to +@code{#f}. The caller is responsible for detecting and reporting +errors. + +@example +(define opts ":-:b:") +(define argc 5) +(define argv '("foo" "-b9" "--f1" "--2=" "--g3=35234.342" "--")) +(define *optind* 1) +(define *optarg* #f) +(require 'qp) +(do ((i 5 (+ -1 i))) + ((zero? i)) + (define opt (getopt-- argc argv opts)) + (print *optind* opt *optarg*))) +@print{} +2 #\b "9" +3 "f1" #f +4 "2" "" +5 "g3" "35234.342" +5 #f "35234.342" +@end example +@end defun + +@node Command Line, System Interface, Getopt, Session Support +@section Command Line + +@code{(require 'read-command)} + +@defun read-command port +@defunx read-command +@code{read-command} converts a @dfn{command line} into a list of strings +suitable for parsing by @code{getopt}. The syntax of command lines +supported resembles that of popular @dfn{shell}s. @code{read-command} +updates @var{port} to point to the first character past the command +delimiter. + +If an end of file is encountered in the input before any characters are +found that can begin an object or comment, then an end of file object is +returned. + +The @var{port} argument may be omitted, in which case it defaults to the +value returned by @code{current-input-port}. + +The fields into which the command line is split are delimited by +whitespace as defined by @code{char-whitespace?}. The end of a command +is delimited by end-of-file or unescaped semicolon (@key{;}) or +@key{newline}. Any character can be literally included in a field by +escaping it with a backslach (@key{\}). + +The initial character and types of fields recognized are: +@table @asis +@item @samp{\} +The next character has is taken literally and not interpreted as a field +delimiter. If @key{\} is the last character before a @key{newline}, +that @key{newline} is just ignored. Processing continues from the +characters after the @key{newline} as though the backslash and +@key{newline} were not there. +@item @samp{"} +The characters up to the next unescaped @key{"} are taken literally, +according to [R4RS] rules for literal strings (@pxref{Strings, , ,r4rs, +Revised(4) Scheme}). +@item @samp{(}, @samp{%'} +One scheme expression is @code{read} starting with this character. The +@code{read} expression is evaluated, converted to a string +(using @code{display}), and replaces the expression in the returned +field. +@item @samp{;} +Semicolon delimits a command. Using semicolons more than one command +can appear on a line. Escaped semicolons and semicolons inside strings +do not delimit commands. +@end table + +@noindent +The comment field differs from the previous fields in that it must be +the first character of a command or appear after whitespace in order to +be recognized. @key{#} can be part of fields if these conditions are +not met. For instance, @code{ab#c} is just the field ab#c. + +@table @samp +@item # +Introduces a comment. The comment continues to the end of the line on +which the semicolon appears. Comments are treated as whitespace by +@code{read-dommand-line} and backslashes before @key{newline}s in +comments are also ignored. +@end table +@end defun + +@node System Interface, Require, Command Line, Session Support +@section System Interface + +If @code{(provided? 'getenv)}: + +@defun getenv name +Looks up @var{name}, a string, in the program environment. If @var{name} is +found a string of its value is returned. Otherwise, @code{#f} is returned. +@end defun + +If @code{(provided? 'system)}: + +@defun system command-string +Executes the @var{command-string} on the computer and returns the +integer status code. +@end defun + + +@node Require, Vicinity, System Interface, Session Support +@section Require + +These variables and procedures are provided by all implementations. + +@defvar *features* +Is a list of symbols denoting features supported in this implementation. +@end defvar + +@defvar *modules* +Is a list of pathnames denoting files which have been loaded. +@end defvar + +@defvar *catalog* +Is an association list of features (symbols) and pathnames which will +supply those features. The pathname can be either a string or a pair. +If pathname is a pair then the first element should be a macro feature +symbol, @code{source}, or @code{compiled}. The cdr of the pathname +should be either a string or a list. +@end defvar + +In the following three functions if @var{feature} is not a symbol it is +assumed to be a pathname.@refill + +@defun provided? feature +Returns @code{#t} if @var{feature} is a member of @code{*features*} or +@code{*modules*} or if @var{feature} is supported by a file already +loaded and @code{#f} otherwise.@refill +@end defun + +@deffn Procedure require feature +If @code{(not (provided? @var{feature}))} it is loaded if @var{feature} +is a pathname or if @code{(assq @var{feature} *catalog*)}. Otherwise an +error is signaled.@refill +@end deffn + +@deffn Procedure provide feature +Assures that @var{feature} is contained in @code{*features*} if +@var{feature} is a symbol and @code{*modules*} otherwise.@refill +@end deffn + +@defun require:feature->path feature +Returns @code{#t} if @var{feature} is a member of @code{*features*} or +@code{*modules*} or if @var{feature} is supported by a file already +loaded. Returns a path if one was found in @code{*catalog*} under the +feature name, and @code{#f} otherwise. The path can either be a string +suitable as an argument to load or a pair as described above for +*catalog*. +@end defun + +Below is a list of features that are automatically determined by +@code{require}. For each item, @code{(provided? '@var{feature})} will +return @code{#t} if that feature is available, and @code{#f} if +not.@refill + +@itemize @bullet +@item +'inexact +@item +'rational +@item +'real +@item +'complex +@item +'bignum +@end itemize + + + + + +@node Vicinity, Configuration, Require, Session Support +@section Vicinity + +A vicinity is a descriptor for a place in the file system. Vicinities +hide from the programmer the concepts of host, volume, directory, and +version. Vicinities express only the concept of a file environment +where a file name can be resolved to a file in a system independent +manner. Vicinities can even be used on @dfn{flat} file systems (which +have no directory structure) by having the vicinity express constraints +on the file name. On most systems a vicinity would be a string. All of +these procedures are file system dependent. + +These procedures are provided by all implementations. + +@defun make-vicinity filename +Returns the vicinity of @var{filename} for use by @code{in-vicinity}. +@end defun + +@defun program-vicinity +Returns the vicinity of the currently loading Scheme code. For an +interpreter this would be the directory containing source code. For a +compiled system (with multiple files) this would be the directory where +the object or executable files are. If no file is currently loading it +the result is undefined. @strong{Warning:} @code{program-vicinity} can +return incorrectl values if your program escapes back into a +@code{load}.@refill +@end defun + +@defun library-vicinity +Returns the vicinity of the shared Scheme library. +@end defun + +@defun implementation-vicinity +Returns the vicinity of the underlying Scheme implementation. This +vicinity will likely contain startup code and messages and a compiler. +@end defun + +@defun user-vicinity +Returns the vicinity of the current directory of the user. On most +systems this is @file{""} (the empty string). +@end defun + +@c @defun scheme-file-suffix +@c Returns the default filename suffix for scheme source files. On most +@c systems this is @samp{.scm}.@refill +@c @end defun + +@defun in-vicinity vicinity filename +Returns a filename suitable for use by @code{slib:load}, +@code{slib:load-source}, @code{slib:load-compiled}, +@code{open-input-file}, @code{open-output-file}, etc. The returned +filename is @var{filename} in @var{vicinity}. @code{in-vicinity} should +allow @var{filename} to override @var{vicinity} when @var{filename} is +an absolute pathname and @var{vicinity} is equal to the value of +@code{(user-vicinity)}. The behavior of @code{in-vicinity} when +@var{filename} is absolute and @var{vicinity} is not equal to the value +of @code{(user-vicinity)} is unspecified. For most systems +@code{in-vicinity} can be @code{string-append}.@refill +@end defun + +@defun sub-vicinity vicinity name +Returns the vicinity of @var{vicinity} restricted to @var{name}. This +is used for large systems where names of files in subsystems could +conflict. On systems with directory structure @code{sub-vicinity} will +return a pathname of the subdirectory @var{name} of +@var{vicinity}.@refill +@end defun + + + +@node Configuration, Input/Output, Vicinity, Session Support +@section Configuration + +These constants and procedures describe characteristics of the Scheme +and underlying operating system. They are provided by all +implementations. + +@defvr Constant char-code-limit +An integer 1 larger that the largest value which can be returned by +@code{char->integer}.@refill +@end defvr + +@defvr Constant most-positive-fixnum +The immediate integer closest to positive infinity. +@end defvr + +@defvr Constant slib:tab +The tab character. +@end defvr + +@defvr Constant slib:form-feed +The form-feed character. +@end defvr + +@defun software-type +Returns a symbol denoting the generic operating system type. For +instance, @code{unix}, @code{vms}, @code{macos}, @code{amiga}, or +@code{ms-dos}. +@end defun + +@defun slib:report-version +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 "2a3" on scm "4e1" on unix +@end example +@end defun + +@defun slib:report +Displays the information of @code{(slib:report-version)} followed by +almost all the information neccessary for submitting a problem report. +An unspecified value is returned. + +@defunx slib:report #t +provides a more verbose listing. + +@defunx slib:report filename +Writes the report to file @file{filename}. + +@example +(slib:report) +@result{} +slib "2a3" on scm "4e1" on unix +(implementation-vicinity) is "/usr/local/src/scm/" +(library-vicinity) is "/usr/local/lib/slib/" +(scheme-file-suffix) is ".scm" +implementation *features* : + bignum complex real rational + inexact vicinity ed getenv + tmpnam system abort transcript + with-file ieee-p1178 rev4-report rev4-optional-procedures + hash object-hash delay eval + dynamic-wind multiarg-apply multiarg/and- logical + defmacro string-port source array-for-each + array full-continuation char-ready? line-i/o + i/o-extensions pipe +implementation *catalog* : + (rev4-optional-procedures . "/usr/local/lib/slib/sc4opt") + ... +@end example +@end defun + +@node Input/Output, Legacy, Configuration, Session Support +@section Input/Output + +These procedures are provided by all implementations. + +@deffn Procedure file-exists? filename +Returns @code{#t} if the specified file exists. Otherwise, returns +@code{#f}. If the underlying implementation does not support this +feature then @code{#f} is always returned. +@end deffn + +@deffn Procedure delete-file filename +Deletes the file specified by @var{filename}. If @var{filename} can not +be deleted, @code{#f} is returned. Otherwise, @code{#t} is +returned.@refill +@end deffn + +@deffn Procedure tmpnam +Returns a pathname for a file which will likely not be used by any other +process. Successive calls to @code{(tmpnam)} will return different +pathnames.@refill +@end deffn + +@deffn Procedure current-error-port +Returns the current port to which diagnostic and error output is +directed. +@end deffn + +@deffn Procedure force-output +@deffnx Procedure force-output port +Forces any pending output on @var{port} to be delivered to the output +device and returns an unspecified value. The @var{port} argument may be +omitted, in which case it defaults to the value returned by +@code{(current-output-port)}.@refill +@end deffn + +@deffn Procedure output-port-width +@deffnx Procedure output-port-width port + +Returns the width of @var{port}, which defaults to +@code{(current-output-port)} if absent. If the width cannot be +determined 79 is returned.@refill +@end deffn + +@deffn Procedure output-port-height +@deffnx Procedure output-port-height port + +Returns the height of @var{port}, which defaults to +@code{(current-output-port)} if absent. If the height cannot be +determined 24 is returned.@refill +@end deffn + +@node Legacy, System, Input/Output, Session Support +@section Legacy + +@defun identity x +@var{identity} returns its argument. + +Example: +@lisp +(identity 3) + @result{} 3 +(identity '(foo bar)) + @result{} (foo bar) +(map identity @var{lst}) + @equiv{} (copy-list @var{lst}) +@end lisp +@end defun + +These were present in Scheme until R4RS (@pxref{Notes, , Language +changes ,r4rs, Revised(4) Scheme}). + +@defvr Constant t +Derfined as @code{#t}. +@end defvr + +@defvr Constant nil +Defined as @code{#f}. +@end defvr + +@defun last-pair l +Returns the last pair in the list @var{l}. Example: +@lisp +(last-pair (cons 1 2)) + @result{} (1 . 2) +(last-pair '(1 2)) + @result{} (2) + @equiv{} (cons 2 '()) +@end lisp +@end defun + +@node System, , Legacy, Session Support +@section System + +These procedures are provided by all implementations. + +@deffn Procedure slib:load-source name +Loads a file of Scheme source code from @var{name} with the default +filename extension used in SLIB. For instance if the filename extension +used in SLIB is @file{.scm} then @code{(slib:load-source "foo")} will +load from file @file{foo.scm}. +@end deffn + +@deffn Procedure slib:load-compiled name +On implementations which support separtely loadable compiled modules, +loads a file of compiled code from @var{name} with the implementation's +filename extension for compiled code appended. +@end deffn + +@deffn Procedure slib:load name +Loads a file of Scheme source or compiled code from @var{name} with the +appropriate suffixes appended. If both source and compiled code are +present with the appropriate names then the implementation will load +just one. It is up to the implementation to choose which one will be +loaded. + +If an implementation does not support compiled code then +@code{slib:load} will be identical to @code{slib:load-source}. +@end deffn + +@deffn Procedure slib:eval obj +@code{eval} returns the value of @var{obj} evaluated in the current top +level environment.@refill +@end deffn + +@deffn Procedure slib:eval-load filename eval +@var{filename} should be a string. If filename names an existing file, +the Scheme source code expressions and definitions are read from the +file and @var{eval} called with them sequentially. The +@code{slib:eval-load} procedure does not affect the values returned by +@code{current-input-port} and @code{current-output-port}.@refill +@end deffn + +@deffn Procedure slib:error arg1 arg2 @dots{} +Outputs an error message containing the arguments, aborts evaluation of +the current form and responds in a system dependent way to the error. +Typical responses are to abort the program or to enter a read-eval-print +loop.@refill +@end deffn + +@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}. +@end deffn + + +@node Optional SLIB Packages, Procedure and Macro Index, Session Support, Top +@chapter Optional SLIB Packages + +Several Scheme packages have been written using SLIB. There are several +reasons why a package might not be included in the SLIB distribution: +@itemize @bullet +@item +Because it requires special hardware or software which is not universal. +@item +Because it is large and of limited interest to most Scheme users. +@item +Because it has copying terms different enough from the other SLIB +packages that its inclusion would cause confusion. +@item +Because it is an application program, rather than a library module. +@item +Because I have been too busy to integrate it. +@end itemize + +Once an optional package is installed (and an entry added to +@code{*catalog*}, the @code{require} mechanism allows it to be called up +and used as easily as any other SLIB package. Some optional packages +(for which @code{*catalog*} already has entries) available from SLIB +sites are: + +@table @asis +@item SLIB-PSD is a portable debugger for Scheme (requires emacs editor). +@lisp +ftp-swiss.ai.mit.edu:pub/scm/slib-psd1-3.tar.gz +prep.ai.mit.edu: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 + +With PSD, you can run a Scheme program in an Emacs buffer, set +breakpoints, single step evaluation and access and modify the program's +variables. It works by instrumenting the original source code, so it +should run with any R4RS compliant Scheme. It has been tested with SCM, +Elk 1.5, and the sci interpreter in the Scheme->C system, but should +work with other Schemes with a minimal amount of porting, if at +all. Includes documentation and user's manual. Written by Pertti +Kellom\"aki, pk@@cs.tut.fi. The Lisp Pointers article describing PSD +(Lisp Pointers VI(1):15-23, January-March 1993) is available as +@lisp +http://www.cs.tut.fi/staff/pk/scheme/psd/article/article.html +@end lisp +@item SLIB-SCHELOG is an embedding of Prolog in Scheme. +@lisp +ftp-swiss.ai.mit.edu:pub/scm/slib-schelog.tar.gz +prep.ai.mit.edu:pub/gnu/jacal/slib-schelog.tar.gz +ftp.maths.tcd.ie:pub/bosullvn/jacal/slib-schelog.tar.gz +ftp.cs.indiana.edu:/pub/scheme-repository/utl/slib-schelog.tar.gz +@end lisp +@end table + +@node Procedure and Macro Index, Variable Index, Optional SLIB Packages, Top +@unnumbered Procedure and Macro Index + +This is an alphabetical list of all the procedures and macros in SLIB. + +@printindex fn + +@node Variable Index, , Procedure and Macro Index, Top +@unnumbered Variable Index + +This is an alphabetical list of all the global variables in SLIB. + +@printindex vr + +@contents +@bye |