path: root/slib.info-4

This is Info file slib.info, produced by Makeinfo-1.64 from the input
file slib.texi.

  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.

  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.


File: slib.info,  Node: Syntactic Closures,  Next: Syntax-Case Macros,  Prev: Macros That Work,  Up: Macros

Syntactic Closures
==================

  `(require 'syntactic-closures)'

 - Function: macro:expand EXPRESSION
 - Function: synclo:expand EXPRESSION
     Returns scheme code with the macros and derived expression types of
     EXPRESSION expanded to primitive expression types.

 - Function: macro:eval EXPRESSION
 - Function: synclo:eval EXPRESSION
     `macro:eval' returns the value of EXPRESSION in the current top
     level environment.  EXPRESSION can contain macro definitions.
     Side effects of EXPRESSION will affect the top level environment.

 - Procedure: macro:load FILENAME
 - Procedure: synclo:load FILENAME
     FILENAME should be a string.  If filename names an existing file,
     the `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 `macro:load' procedure does not affect the
     values returned by `current-input-port' and `current-output-port'.

Syntactic Closure Macro Facility
--------------------------------

                  A Syntactic Closures Macro Facility

                            by Chris Hanson

                            9 November 1991

  This document describes "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 `Revised^4
Report on Scheme.' This document is an addendum to that report.

  The syntactic closures facility extends the BNF rule for TRANSFORMER
SPEC to allow a new keyword that introduces a low-level macro
transformer:
     TRANSFORMER SPEC := (transformer EXPRESSION)

  Additionally, the following procedures are added:
     make-syntactic-closure
     capture-syntactic-environment
     identifier?
     identifier=?

  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
"identifiers", which extend the syntactic closure mechanism to be
compatible with `syntax-rules'.

Terminology
...........

  This section defines the concepts and data types used by the syntactic
closures facility.

     "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 `set!' special form is also a
     form.  Examples of forms:
          17
          #t
          car
          (+ x 4)
          (lambda (x) x)
          (define pi 3.14159)
          if
          define

     An "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 `symbol?'.  Macro transformers rarely distinguish
     symbols from aliases, referring to both as identifiers.

     A "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.

     A "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.

Transformer Definition
......................

  This section describes the `transformer' special form and the
procedures `make-syntactic-closure' and `capture-syntactic-environment'.

 - Syntax: transformer EXPRESSION
     Syntax: It is an error if this syntax occurs except as a
     TRANSFORMER SPEC.

     Semantics: The 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 `transformer' expression appears (for example,
     `let-syntax').

     A "macro transformer" is a procedure that takes two arguments, a
     form and a syntactic environment, and returns a new form.  The
     first argument, the "input form", is the form in which the macro
     keyword occurred.  The second argument, the "usage environment",
     is the syntactic environment in which the input form occurred.
     The result of the transformer, the "output form", is automatically
     closed in the "transformer environment", which is the syntactic
     environment in which the `transformer' expression occurred.

     For example, here is a definition of a push macro using
     `syntax-rules':
          (define-syntax  push
            (syntax-rules ()
              ((push item list)
               (set! list (cons item list)))))

     Here is an equivalent definition using `transformer':
          (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))))))

     In this example, the identifiers `set!' and `cons' are closed in
     the transformer environment, and thus will not be affected by the
     meanings of those identifiers in the usage environment `env'.

     Some macros may be non-hygienic by design.  For example, the
     following defines a loop macro that implicitly binds `exit' to an
     escape procedure.  The binding of `exit' is intended to capture
     free references to `exit' in the body of the loop, so `exit' must
     be left free when the body is closed:
          (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))))))))

     To assign meanings to the identifiers in a form, use
     `make-syntactic-closure' to close the form in a syntactic
     environment.

 - Function: make-syntactic-closure ENVIRONMENT FREE-NAMES FORM
     ENVIRONMENT must be a syntactic environment, FREE-NAMES must be a
     list of identifiers, and FORM must be a form.
     `make-syntactic-closure' constructs and returns a syntactic closure
     of FORM in ENVIRONMENT, which can be used anywhere that FORM could
     have been used.  All the identifiers used in FORM, except those
     explicitly excepted by FREE-NAMES, obtain their meanings from
     ENVIRONMENT.

     Here is an example where FREE-NAMES is something other than the
     empty list.  It is instructive to compare the use of FREE-NAMES in
     this example with its use in the `loop' example above: the examples
     are similar except for the source of the identifier being left
     free.
          (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))))))

     `let1' is a simplified version of `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
     `let1' must be left free, so that it can be properly captured by
     the `lambda' in the output form.

     To obtain a syntactic environment other than the usage
     environment, use `capture-syntactic-environment'.

 - Function: capture-syntactic-environment PROCEDURE
     `capture-syntactic-environment' returns a form that will, when
     transformed, call PROCEDURE on the current syntactic environment.
     PROCEDURE should compute and return a new form to be transformed,
     in that same syntactic environment, in place of the form.

     An example will make this clear.  Suppose we wanted to define a
     simple `loop-until' keyword equivalent to
          (define-syntax loop-until
            (syntax-rules ()
              ((loop-until id init test return step)
               (letrec ((loop
                         (lambda (id)
                           (if test return (loop step)))))
                 (loop init)))))

     The following attempt at defining `loop-until' has a subtle bug:
          (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 '())))))))

     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 `id' identifier free in the `test', `return', and
     `step' expressions, so that it will be captured by the binding
     introduced by the `lambda' expression.  Unfortunately it uses the
     identifiers `if' and `loop' within that `lambda' expression, so if
     the user of `loop-until' just happens to use, say, `if' for the
     identifier, it will be inadvertently captured.

     The syntactic environment that `if' and `loop' want to be exposed
     to is the one just outside the `lambda' expression: before the
     user's identifier is added to the syntactic environment, but after
     the identifier loop has been added.
     `capture-syntactic-environment' captures exactly that environment
     as follows:
          (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 '())))))))

     In this case, having captured the desired syntactic environment,
     it is convenient to construct syntactic closures of the
     identifiers `if' and the `loop' and use them in the body of the
     `lambda'.

     A common use of `capture-syntactic-environment' is to get the
     transformer environment of a macro transformer:
          (transformer
           (lambda (exp env)
             (capture-syntactic-environment
              (lambda (transformer-env)
                ...))))

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 `syntax-rules' facility.

  As discussed earlier, an identifier is either a symbol or an "alias".
An alias is implemented as a syntactic closure whose "form" is an
identifier:
     (make-syntactic-closure env '() 'a)
        => an "alias"

  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 `lambda' or
`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.

  Aliases are used in the implementation of the high-level facility
`syntax-rules'.  A macro transformer created by `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.

 - Function: identifier? OBJECT
     Returns `#t' if OBJECT is an identifier, otherwise returns `#f'.
     Examples:
          (identifier? 'a)
             => #t
          (identifier? (make-syntactic-closure env '() 'a))
             => #t
          (identifier? "a")
             => #f
          (identifier? #\a)
             => #f
          (identifier? 97)
             => #f
          (identifier? #f)
             => #f
          (identifier? '(a))
             => #f
          (identifier? '#(a))
             => #f

     The predicate `eq?' is used to determine if two identifers are
     "the same".  Thus `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 `cond' macro uses the symbol `else' to identify the
     final clause in the conditional.  A macro transformer for `cond'
     cannot just look for the symbol `else', because the `cond' form
     might be the output of another macro transformer that replaced the
     symbol `else' with an alias.  Instead the transformer must look
     for an identifier that "means the same thing" in the usage
     environment as the symbol `else' means in the transformer
     environment.

 - Function: identifier=? ENVIRONMENT1 IDENTIFIER1 ENVIRONMENT2
          IDENTIFIER2
     ENVIRONMENT1 and ENVIRONMENT2 must be syntactic environments, and
     IDENTIFIER1 and IDENTIFIER2 must be identifiers.  `identifier=?'
     returns `#t' if the meaning of IDENTIFIER1 in ENVIRONMENT1 is the
     same as that of IDENTIFIER2 in ENVIRONMENT2, otherwise it returns
     `#f'.  Examples:

          (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))))
             => (#t #f)

          (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))))
             => (#f #t)

Acknowledgements
................

  The syntactic closures facility was invented by Alan Bawden and
Jonathan Rees.  The use of aliases to implement `syntax-rules' was
invented by Alan Bawden (who prefers to call them "synthetic names").
Much of this proposal is derived from an earlier proposal by Alan
Bawden.


File: slib.info,  Node: Syntax-Case Macros,  Next: Fluid-Let,  Prev: Syntactic Closures,  Up: Macros

Syntax-Case Macros
==================

  `(require 'syntax-case)'

 - Function: macro:expand EXPRESSION
 - Function: syncase:expand EXPRESSION
     Returns scheme code with the macros and derived expression types of
     EXPRESSION expanded to primitive expression types.

 - Function: macro:eval EXPRESSION
 - Function: syncase:eval EXPRESSION
     `macro:eval' returns the value of EXPRESSION in the current top
     level environment.  EXPRESSION can contain macro definitions.
     Side effects of EXPRESSION will affect the top level environment.

 - Procedure: macro:load FILENAME
 - Procedure: syncase:load FILENAME
     FILENAME should be a string.  If filename names an existing file,
     the `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 `macro:load' procedure does not affect the
     values returned by `current-input-port' and `current-output-port'.

  This is version 2.1 of `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:

   * Removing white space from `expand.pp' to save space in the
     distribution.  This file is not meant for human readers anyway...

   * Removed a couple of Chez scheme dependencies.

   * Renamed global variables used to minimize the possibility of name
     conflicts.

   * Adding an SLIB-specific initialization file.

   * Removing a couple extra files, most notably the documentation (but
     see below).

  If you wish, you can see exactly what changes were done by reading the
shell script in the 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 `syntax-case',
however, you should get these files and print them out on a PostScript
printer.  They are available with the original `syntax-case'
distribution by anonymous FTP in
`cs.indiana.edu:/pub/scheme/syntax-case'.

  In order to use syntax-case from an interactive top level, execute:
     (require 'syntax-case)
     (require 'repl)
     (repl:top-level macro:eval)
  See the section Repl (*Note Repl::) for more information.

  To check operation of syntax-case get
`cs.indiana.edu:/pub/scheme/syntax-case', and type
     (require 'syntax-case)
     (syncase:sanity-check)

  Beware that `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).

Notes
-----

  All R4RS syntactic forms are defined, including `delay'.  Along with
`delay' are simple definitions for `make-promise' (into which `delay'
expressions expand) and `force'.

  `syntax-rules' and `with-syntax' (described in `TR356') are defined.

  `syntax-case' is actually defined as a macro that expands into calls
to the procedure `syntax-dispatch' and the core form `syntax-lambda';
do not redefine these names.

  Several other top-level bindings not documented in TR356 are created:
     the "hooks" in `hooks.ss'

     the `build-' procedures in `output.ss'

     `expand-syntax' (the expander)

  The syntax of define has been extended to allow `(define ID)', which
assigns ID to some unspecified value.

  We have attempted to maintain R4RS compatibility where possible.  The
incompatibilities should be confined to `hooks.ss'.  Please let us know
if there is some incompatibility that is not flagged as such.

  Send bug reports, comments, suggestions, and questions to Kent Dybvig
(dyb@iuvax.cs.indiana.edu).

Note from maintainer
--------------------

  Included with the `syntax-case' files was `structure.scm' which
defines a macro `define-structure'.  There is no documentation for this
macro and it is not used by any code in SLIB.


File: slib.info,  Node: Fluid-Let,  Next: Yasos,  Prev: Syntax-Case Macros,  Up: Macros

Fluid-Let
=========

  `(require 'fluid-let)'

 - Syntax: fluid-let `(BINDINGS ...)' FORMS...

     (fluid-let ((VARIABLE INIT) ...)
        EXPRESSION EXPRESSION ...)

  The INITs are evaluated in the current environment (in some
unspecified order), the current values of the VARIABLEs are saved, the
results are assigned to the VARIABLEs, the EXPRESSIONs are evaluated
sequentially in the current environment, the VARIABLEs are restored to
their original values, and the value of the last EXPRESSION is returned.

  The syntax of this special form is similar to that of `let', but
`fluid-let' temporarily rebinds existing VARIABLEs.  Unlike `let',
`fluid-let' creates no new bindings; instead it *assigns* the values of
each INIT to the binding (determined by the rules of lexical scoping)
of its corresponding VARIABLE.


File: slib.info,  Node: Yasos,  Prev: Fluid-Let,  Up: Macros

Yasos
=====

  `(require 'oop)' or `(require 'yasos)'

  `Yet Another Scheme Object System' is a simple object system for
Scheme based on the paper by Norman Adams and Jonathan Rees: `Object
Oriented Programming in Scheme', Proceedings of the 1988 ACM Conference
on LISP and Functional Programming, July 1988 [ACM #552880].

  Another reference is:

  Ken Dickey.  Scheming with Objects `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.


File: slib.info,  Node: Yasos terms,  Next: Yasos interface,  Prev: Yasos,  Up: Yasos

Terms
-----

"Object"
     Any Scheme data object.

"Instance"
     An instance of the OO system; an "object".

"Operation"
     A METHOD.

*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
     `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 "classes" and no meta-ANYTHING.  Method
     dispatch is by a procedure call a la CLOS rather than by `send'
     syntax a la Smalltalk.

*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.


File: slib.info,  Node: Yasos interface,  Next: Setters,  Prev: Yasos terms,  Up: Yasos

Interface
---------

 - Syntax: define-operation `('OPNAME SELF ARG ...`)' DEFAULT-BODY
     Defines a default behavior for data objects which don't handle the
     operation OPNAME.  The default default behavior (for an empty
     DEFAULT-BODY) is to generate an error.

 - Syntax: define-predicate OPNAME?
     Defines a predicate OPNAME?, usually used for determining the
     "type" of an object, such that `(OPNAME? OBJECT)' returns `#t' if
     OBJECT has an operation OPNAME? and `#f' otherwise.

 - Syntax: object `((NAME SELF ARG ...) BODY)' ...
     Returns an object (an instance of the object system) with
     operations.  Invoking `(NAME OBJECT ARG ...' executes the BODY of
     the OBJECT with SELF bound to OBJECT and with argument(s) ARG....

 - Syntax: object-with-ancestors `(('ANCESTOR1 INIT1`)' ...`)'
          OPERATION ...
     A `let'-like form of `object' for multiple inheritance.  It
     returns an object inheriting the behaviour of 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.

 - Syntax: operate-as COMPONENT OPERATION SELF ARG ...
     Used in an operation definition (of SELF) to invoke the OPERATION
     in an ancestor COMPONENT but maintain the object's identity.  Also
     known as "send-to-super".

 - Procedure: print OBJ PORT
     A default `print' operation is provided which is just `(format
     PORT OBJ)' (*Note Format::) for non-instances and prints OBJ
     preceded by `#<INSTANCE>' for instances.

 - Function: size OBJ
     The default method returns the number of elements in OBJ if it is
     a vector, string or list, `2' for a pair, `1' for a character and
     by default id an error otherwise.  Objects such as collections
     (*Note Collections::) may override the default in an obvious way.


File: slib.info,  Node: Setters,  Next: Yasos examples,  Prev: Yasos interface,  Up: Yasos

Setters
-------

  "Setters" implement "generalized locations" for objects associated
with some sort of mutable state.  A "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 (*Note Yasos::).
Several setters are predefined, corresponding to getters `car', `cdr',
`string-ref' and `vector-ref' e.g., `(setter car)' is equivalent to
`set-car!'.

  This implementation of setters is similar to that in Dylan(TM)
(`Dylan: An object-oriented dynamic language', Apple Computer Eastern
Research and Technology).  Common LISP provides similar facilities
through `setf'.

 - Function: setter GETTER
     Returns the setter for the procedure GETTER.  E.g., since
     `string-ref' is the getter corresponding to a setter which is
     actually `string-set!':
          (define foo "foo")
          ((setter string-ref) foo 0 #\F) ; set element 0 of foo
          foo => "Foo"

 - Syntax: set PLACE NEW-VALUE
     If PLACE is a variable name, `set' is equivalent to `set!'.
     Otherwise, 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 `set' is usually unspecified unless
     used with a setter whose definition guarantees to return a useful
     value.
          (set (string-ref foo 2) #\O)  ; generalized location with getter
          foo => "FoO"
          (set foo "foo")               ; like set!
          foo => "foo"

 - Procedure: add-setter GETTER SETTER
     Add procedures GETTER and SETTER to the (inaccessible) list of
     valid setter/getter pairs.  SETTER implements the store operation
     corresponding to the GETTER access operation for the relevant
     state.  The return value is unspecified.

 - Procedure: remove-setter-for GETTER
     Removes the setter corresponding to the specified GETTER from the
     list of valid setters.  The return value is unspecified.

 - Syntax: define-access-operation GETTER-NAME
     Shorthand for a Yasos `define-operation' defining an operation
     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.


File: slib.info,  Node: Yasos examples,  Prev: Setters,  Up: Yasos

Examples
--------

     (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)
     => "#<Cell: 1>"
     (set (fetch foo) 2)
     =>
     (print foo #f)
     => "#<Cell: 2>"
     (fetch foo)
     => 2


File: slib.info,  Node: Numerics,  Next: Procedures,  Prev: Macros,  Up: Top

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::


File: slib.info,  Node: Bit-Twiddling,  Next: Modular Arithmetic,  Prev: Numerics,  Up: Numerics

Bit-Twiddling
=============

  `(require 'logical)'

  The bit-twiddling functions are made available through the use of the
`logical' package.  `logical' is loaded by inserting `(require
'logical)' before the code that uses these functions.

 - Function: logand N1 N1
     Returns the integer which is the bit-wise AND of the two integer
     arguments.

     Example:
          (number->string (logand #b1100 #b1010) 2)
             => "1000"

 - Function: logior N1 N2
     Returns the integer which is the bit-wise OR of the two integer
     arguments.

     Example:
          (number->string (logior #b1100 #b1010) 2)
             => "1110"

 - Function: logxor N1 N2
     Returns the integer which is the bit-wise XOR of the two integer
     arguments.

     Example:
          (number->string (logxor #b1100 #b1010) 2)
             => "110"

 - Function: lognot N
     Returns the integer which is the 2s-complement of the integer
     argument.

     Example:
          (number->string (lognot #b10000000) 2)
             => "-10000001"
          (number->string (lognot #b0) 2)
             => "-1"

 - Function: logtest J K
          (logtest j k) == (not (zero? (logand j k)))
          
          (logtest #b0100 #b1011) => #f
          (logtest #b0100 #b0111) => #t

 - Function: logbit? INDEX J
          (logbit? index j) == (logtest (integer-expt 2 index) j)
          
          (logbit? 0 #b1101) => #t
          (logbit? 1 #b1101) => #f
          (logbit? 2 #b1101) => #t
          (logbit? 3 #b1101) => #t
          (logbit? 4 #b1101) => #f

 - Function: ash INT COUNT
     Returns an integer equivalent to `(inexact->exact (floor (* INT
     (expt 2 COUNT))))'.

     Example:
          (number->string (ash #b1 3) 2)
             => "1000"
          (number->string (ash #b1010 -1) 2)
             => "101"

 - Function: logcount N
     Returns the number of bits in integer 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:
          (logcount #b10101010)
             => 4
          (logcount 0)
             => 0
          (logcount -2)
             => 1

 - Function: integer-length N
     Returns the number of bits neccessary to represent N.

     Example:
          (integer-length #b10101010)
             => 8
          (integer-length 0)
             => 0
          (integer-length #b1111)
             => 4

 - Function: integer-expt N K
     Returns N raised to the non-negative integer exponent K.

     Example:
          (integer-expt 2 5)
             => 32
          (integer-expt -3 3)
             => -27

 - Function: bit-extract N START END
     Returns the integer composed of the START (inclusive) through END
     (exclusive) bits of N.  The STARTth bit becomes the 0-th bit in
     the result.

     Example:
          (number->string (bit-extract #b1101101010 0 4) 2)
             => "1010"
          (number->string (bit-extract #b1101101010 4 9) 2)
             => "10110"


File: slib.info,  Node: Modular Arithmetic,  Next: Prime Testing and Generation,  Prev: Bit-Twiddling,  Up: Numerics

Modular Arithmetic
==================

  `(require 'modular)'

 - Function: extended-euclid N1 N2
     Returns a list of 3 integers `(d x y)' such that d = gcd(N1, N2) =
     N1 * x + N2 * y.

 - Function: symmetric:modulus N
     Returns `(quotient (+ -1 n) -2)' for positive odd integer N.

 - Function: modulus->integer MODULUS
     Returns the non-negative integer characteristic of the ring formed
     when MODULUS is used with `modular:' procedures.

 - Function: modular:normalize MODULUS N
     Returns the integer `(modulo N (modulus->integer MODULUS))' in the
     representation specified by MODULUS.

The rest of these functions assume normalized arguments; That is, the
arguments are constrained by the following table:

For all of these functions, if the first argument (MODULUS) is:
`positive?'
     Work as before.  The result is between 0 and MODULUS.

`zero?'
     The arguments are treated as integers.  An integer is returned.

`negative?'
     The arguments and result are treated as members of the integers
     modulo `(+ 1 (* -2 MODULUS))', but with "symmetric"
     representation; i.e. `(<= (- MODULUS) N MODULUS)'.

If all the arguments are fixnums the computation will use only fixnums.

 - Function: modular:invertable? MODULUS K
     Returns `#t' if there exists an integer n such that K * n == 1 mod
     MODULUS, and `#f' otherwise.

 - Function: modular:invert MODULUS K2
     Returns an integer n such that 1 = (n * K2) mod MODULUS.  If K2
     has no inverse mod MODULUS an error is signaled.

 - Function: modular:negate MODULUS K2
     Returns (-K2) mod MODULUS.

 - Function: modular:+ MODULUS K2 K3
     Returns (K2 + K3) mod MODULUS.

 - Function: modular:- MODULUS K2 K3
     Returns (K2 - K3) mod MODULUS.

 - Function: modular:* MODULUS K2 K3
     Returns (K2 * K3) mod MODULUS.

     The Scheme code for `modular:*' with negative MODULUS is not
     completed for fixnum-only implementations.

 - Function: modular:expt MODULUS K2 K3
     Returns (K2 ^ K3) mod MODULUS.


File: slib.info,  Node: Prime Testing and Generation,  Next: Prime Factorization,  Prev: Modular Arithmetic,  Up: Numerics

Prime Testing and Generation
============================

  `(require 'primes)'

  This package tests and generates prime numbers.  The strategy used is
as follows:

     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.

     Second, apply the Miller-Rabin primality test to detect (with high
     probability) any remaining composites.

  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 *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.

 - Function: probably-prime? CANDIDATE
 - Function: probably-prime? CANDIDATE ITER
     Returns `#t' if `candidate' is probably prime.  The optional
     parameter `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 `(1/4)^iter'.  The default value of
     `iter' is 15, which makes the probability less than 1 in 10^9.


 - Function: primes< START COUNT
 - Function: primes< START COUNT ITER
 - Function: primes> START COUNT
 - Function: primes> START COUNT ITER
     Returns a list of the first `count' odd probable primes less (more)
     than or equal to `start'.  The optional parameter `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 `(1/4)^iter'.  The default value
     of `iter' is 15, which makes the probability less than 1 in 10^9.


* Menu:

* The Miller-Rabin Test::       How the Miller-Rabin test works


File: slib.info,  Node: The Miller-Rabin Test,  Prev: Prime Testing and Generation,  Up: Prime Testing and Generation

Theory
------

  Rabin and Miller's result can be summarized as follows.  Let `p' (the
candidate prime) be any odd integer greater than 2.  Let `b' (the
"base") be an integer in the range `2 ... p-1'.  There is a fairly
simple Boolean function--call it `C', for "Composite"--with the
following properties:
     If `p' is prime, `C(p, b)' is false for all `b' in the range `2
     ... p-1'.

     If `p' is composite, `C(p, b)' is false for at most 1/4 of all `b'
     in the range ` 2 ... p-1'.  (If the test fails for base `b', `p'
     is called a *strong pseudo-prime to base `b'*.)

  For details of `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
`p'.  If we had time to test `(1/4)p + 1' different bases, we could
definitively determine the primality of `p'.  For large candidates,
that would take much too long--much longer than the simple approach of
dividing by all numbers up to `sqrt(p)'.  This is where probability
enters the picture.

  Suppose we have some candidate prime `p'.  Pick a random integer `b'
in the range `2 ... p-1'.  Compute `C(p,b)'.  If `p' is prime, the
result will certainly be false.  If `p' is composite, the probability
is at most 1/4 that the result will be false (demonstrating that `p' is
a strong pseudoprime to base `b').  The test can be repeated with other
random bases.  If `p' is prime, each test is certain to return false.
If `p' is composite, the probability of `C(p,b)' returning false is at
most 1/4 for each test.  Since the `b' are chosen at random, the tests
outcomes are independent. So if `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 *all* candidates `p'.  However,
if the candidate `p' is picked at random, the probability of the
Miller-Rabin test failing is much less than the computed bound.  This
is because, for *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 *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.


File: slib.info,  Node: Prime Factorization,  Next: Random Numbers,  Prev: Prime Testing and Generation,  Up: Numerics

Prime Factorization
===================

  `(require 'factor)'

 - Function: factor K
     Returns a list of the prime factors of K.  The order of the
     factors is unspecified.  In order to obtain a sorted list do
     `(sort! (factor k) <)'.

  *Note:* The rest of these procedures implement the Solovay-Strassen
primality test.  This test has been superseeded by the faster *Note
probably-prime?: Prime Testing and Generation.  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, `A Fast Monte-Carlo Test for
Primality', SIAM Journal on Computing, 1977, pp 84-85.

 - Function: jacobi-symbol P Q
     Returns the value (+1, -1, or 0) of the Jacobi-Symbol of exact
     non-negative integer P and exact positive odd integer Q.

 - Function: prime? P
     Returns `#f' if P is composite; `#t' if P is prime.  There is a
     slight chance `(expt 2 (- prime:trials))' that a composite will
     return `#t'.

 - Function: prime:trials
     Is the maxinum number of iterations of Solovay-Strassen that will
     be done to test a number for primality.


File: slib.info,  Node: Random Numbers,  Next: Cyclic Checksum,  Prev: Prime Factorization,  Up: Numerics

Random Numbers
==============

  `(require 'random)'

 - Procedure: random N
 - Procedure: random N STATE
     Accepts a positive integer or real N and returns a number of the
     same type between zero (inclusive) and N (exclusive).  The values
     returned have a uniform distribution.

     The optional argument STATE must be of the type produced by
     `(make-random-state)'.  It defaults to the value of the variable
     `*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 `random' operation.

 - Variable: *random-state*
     Holds a data structure that encodes the internal state of the
     random-number generator that `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.

 - Procedure: make-random-state
 - Procedure: make-random-state STATE
     Returns a new object of type suitable for use as the value of the
     variable `*random-state*' and as a second argument to `random'.
     If argument STATE is given, a copy of it is returned.  Otherwise a
     copy of `*random-state*' is returned.

  If inexact numbers are support by the Scheme implementation,
`randinex.scm' will be loaded as well.  `randinex.scm' contains
procedures for generating inexact distributions.

 - Procedure: random:uniform STATE
     Returns an uniformly distributed inexact real random number in the
     range between 0 and 1.

 - Procedure: random:solid-sphere! VECT
 - Procedure: random:solid-sphere! VECT STATE
     Fills VECT with inexact real random numbers the sum of whose
     squares is less than 1.0.  Thinking of VECT as coordinates in
     space of dimension N = `(vector-length VECT)', the coordinates are
     uniformly distributed within the unit N-shere.  The sum of the
     squares of the numbers is returned.

 - Procedure: random:hollow-sphere! VECT
 - Procedure: random:hollow-sphere! VECT STATE
     Fills VECT with inexact real random numbers the sum of whose
     squares is equal to 1.0.  Thinking of VECT as coordinates in space
     of dimension n = `(vector-length VECT)', the coordinates are
     uniformly distributed over the surface of the unit n-shere.

 - Procedure: random:normal
 - 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 M and
     standard deviation D use `(+ M (* D (random:normal)))'.

 - Procedure: random:normal-vector! VECT
 - Procedure: random:normal-vector! VECT STATE
     Fills VECT with inexact real random numbers which are independent
     and standard normally distributed (i.e., with mean 0 and variance
     1).

 - Procedure: random:exp
 - Procedure: random:exp STATE
     Returns an inexact real in an exponential distribution with mean
     1.  For an exponential distribution with mean U use (* U
     (random:exp)).