diff options
Diffstat (limited to 'slib.info-4')
| -rw-r--r-- | slib.info-4 | 1248 |
1 files changed, 1248 insertions, 0 deletions
diff --git a/slib.info-4 b/slib.info-4 new file mode 100644 index 0000000..3d3da19 --- /dev/null +++ b/slib.info-4 @@ -0,0 +1,1248 @@ +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)). + |