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 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 `#' 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) "#" "~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 "#" (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 "#" (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 "#" (fetch self)))))) (define-access-operation fetch) (add-setter fetch store!) (define foo (make-cell 1)) (print foo #f) => "#" (set (fetch foo) 2) => (print foo #f) => "#" (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)).