Go to the previous, next section.

Procedures

Anything that doesn't fall neatly into any of the other categories winds up here.

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: 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 #b10101010 0 4) 2)
   => "1010"
(number->string (bit-extract #b11111111 4 9) 2)
   => "1111"

Common List Functions

(require 'common-list-functions)

The procedures below follow the Common LISP equivalents apart from optional arguments in some cases.

List construction

Function: make-list k . init

make-list creates and returns a list of k elements. If init is included, all elements in the list are initialized to init.

Example:

(make-list 3)
   => (#<unspecified> #<unspecified> #<unspecified>)
(make-list 5 'foo)
   => (foo foo foo foo foo)

Function: list* x . y

Works like list except that the cdr of the last pair is the last argument unless there is only one argument, when the result is just that argument. Sometimes called cons*. E.g.:

(list* 1)
   => 1
(list* 1 2 3)
   => (1 2 . 3)
(list* 1 2 '(3 4))
   => (1 2 3 4)
(list* args '())
   == (list args)

Function: copy-list lst

copy-list makes a copy of lst using new pairs and returns it. Only the top level of the list is copied, i.e., pairs forming elements of the copied list remain eq? to the corresponding elements of the original; the copy is, however, not eq? to the original, but is equal? to it.

Example:

(copy-list '(foo foo foo))
   => (foo foo foo)
(define q '(foo bar baz bang))
(define p q)
(eq? p q)
   => #t
(define r (copy-list q))
(eq? q r)
   => #f
(equal? q r)
   => #t
(define bar '(bar))
(eq? bar (car (copy-list (list bar 'foo))))
=> #t
   @end lisp







Lists as sets

eq? is used to test for membership by all the procedures below
which treat lists as sets.

Function: adjoin e l

adjoin returns the adjoint of the element e and the list
l.  That is, if e is in l, adjoin returns
l, otherwise, it returns (cons e l).
Example:
(adjoin 'baz '(bar baz bang))
   => (bar baz bang)
(adjoin 'foo '(bar baz bang))
   => (foo bar baz bang)



Function: union l1 l2

union returns the combination of l1 and l2 with
duplicates removed.

Example:
(union '(1 2 3 4) '(5 6 7 8))
   => (4 3 2 1 5 6 7 8)
(union '(1 2 2 1) '(3 4 1 8))
   => (2 3 4 1 8)



Function: intersection l1 l2

intersection returns all elements that are in both l1 and
l2.

Example:
(intersection '(1 2 3 4) '(3 4 5 6))
   => (3 4)
(intersection '(1 2 3 4) '(5 6 7 8))
   => ()



Function: set-difference l1 l2

set-difference returns the union of all elements that are in
l1 but not in l2.

Example:
(set-difference '(1 2 3 4) '(3 4 5 6))
   => (1 2)
(set-difference '(1 2 3 4) '(1 2 3 4 5 6))
   => ()



Function: member-if pred lst

member-if returns lst if (pred element)
is #t for any element in lst.  Returns #f if
pred does not apply to any element in lst.

Example:
(member-if vector? '(1 2 3 4))
   => #f
(member-if number? '(1 2 3 4))
   => (1 2 3 4)



Function: some pred lst . more-lsts

pred is a boolean function of as many arguments as there are list
arguments to some i.e., lst plus any optional arguments.
pred is applied to successive elements of the list arguments in
order.  some returns #t as soon as one of these
applications returns #t, and is #f if none returns
#t.  All the lists should have the same length.

Example:
(some odd? '(1 2 3 4))
   => #t

(some odd? '(2 4 6 8))
   => #f

(some > '(2 3) '(1 4))
   => #f



Function: every pred lst . more-lsts

every is analogous to some except it returns #t if
every application of pred is #t and #f
otherwise.

Example:
(every even? '(1 2 3 4))
   => #f

(every even? '(2 4 6 8))
   => #t

(every > '(2 3) '(1 4))
   => #f



Function: notany pred . lst

notany is analogous to some but returns #t if no
application of pred returns #t or #f as soon as any
one does.


Function: notevery pred . lst

notevery is analogous to some but returns #t as soon
as an application of pred returns #f, and #f
otherwise.

Example:
(notevery even? '(1 2 3 4))
   => #t

(notevery even? '(2 4 6 8))
   => #f



Function: find-if pred lst

find-if searches for the first element in lst such
that (pred element) returns #t.  If it finds
any such element in lst, element is returned.
Otherwise, #f is returned.

Example:
(find-if number? '(foo 1 bar 2))
   => 1

(find-if number? '(foo bar baz bang))
   => #f

(find-if symbol? '(1 2 foo bar))
   => foo



Function: remove elt lst

remove removes all occurrences of elt from lst using
eqv? to test for equality and returns everything that's left.
N.B.: other implementations (Chez, Scheme->C and T, at least) use
equal? as the equality test.

Example:
(remove 1 '(1 2 1 3 1 4 1 5))
   => (2 3 4 5)

(remove 'foo '(bar baz bang))
   => (bar baz bang)



Function: remove-if pred lst

remove-if removes all elements from lst where
(pred element) is #t and returns everything
that's left.

Example:
(remove-if number? '(1 2 3 4))
   => ()

(remove-if even? '(1 2 3 4 5 6 7 8))
   => (1 3 5 7)



Function: remove-if-not pred lst

remove-if-not removes all elements from lst for which
(pred element) is #f and returns everything that's
left.

Example:
(remove-if-not number? '(foo bar baz))
   => ()
(remove-if-not odd? '(1 2 3 4 5 6 7 8))
   => (1 3 5 7)



Function: has-duplicates? lst

returns #t if 2 members of lst are equal?, #f
otherwise.
Example:
(has-duplicates? '(1 2 3 4))
   => #f

(has-duplicates? '(2 4 3 4))
   => #t


Lists as sequences


Function: position obj lst

position returns the 0-based position of obj in lst,
or #f if obj does not occur in lst.

Example:
(position 'foo '(foo bar baz bang))
   => 0
(position 'baz '(foo bar baz bang))
   => 2
(position 'oops '(foo bar baz bang))
   => #f



Function: reduce p lst

reduce combines all the elements of a sequence using a binary
operation (the combination is left-associative).  For example, using
+, one can add up all the elements.  reduce allows you to
apply a function which accepts only two arguments to more than 2
objects.  Functional programmers usually refer to this as foldl.
collect:reduce (See section Collections) provides a version of
collect generalized to collections.

Example:
(reduce + '(1 2 3 4))
   => 10
(define (bad-sum . l) (reduce + l))
(bad-sum 1 2 3 4)
   == (reduce + (1 2 3 4))
   == (+ (+ (+ 1 2) 3) 4)
=> 10
(bad-sum)
   == (reduce + ())
   => ()
(reduce string-append '("hello" "cruel" "world"))
   == (string-append (string-append "hello" "cruel") "world")
   => "hellocruelworld"
(reduce anything '())
   => ()
(reduce anything '(x))
   => x


What follows is a rather non-standard implementation of reverse
in terms of reduce and a combinator elsewhere called
C.

;;; Contributed by Jussi Piitulainen (jpiitula@ling.helsinki.fi)

(define commute
  (lambda (f)
    (lambda (x y)
      (f y x))))

(define reverse
  (lambda (args)
    (reduce-init (commute cons) args)))



Function: reduce-init p init lst

reduce-init is the same as reduce, except that it implicitly
inserts init at the start of the list.  reduce-init is
preferred if you want to handle the null list, the one-element, and
lists with two or more elements consistently.  It is common to use the
operator's idempotent as the initializer.  Functional programmers
usually call this foldl.

Example:
(define (sum . l) (reduce-init + 0 l))
(sum 1 2 3 4)
   == (reduce-init + 0 (1 2 3 4))
   == (+ (+ (+ (+ 0 1) 2) 3) 4)
   => 10
(sum)
   == (reduce-init + 0 '())
   => 0

(reduce-init string-append "@" '("hello" "cruel" "world"))
==
(string-append (string-append (string-append "@" "hello")
                               "cruel")
               "world")
=> "@hellocruelworld"


Given a differentiation of 2 arguments, diff, the following will
differentiate by any number of variables.
(define (diff* exp . vars)
  (reduce-init diff exp vars))


Example:
;;; Real-world example:  Insertion sort using reduce-init.

(define (insert l item)
  (if (null? l)
      (list item)
      (if (< (car l) item)
          (cons (car l) (insert (cdr l) item))
          (cons item l))))
(define (insertion-sort l) (reduce-init insert '() l))

(insertion-sort '(3 1 4 1 5)
   == (reduce-init insert () (3 1 4 1 5))
   == (insert (insert (insert (insert (insert () 3) 1) 4) 1) 5)
   == (insert (insert (insert (insert (3)) 1) 4) 1) 5)
   == (insert (insert (insert (1 3) 4) 1) 5)
   == (insert (insert (1 3 4) 1) 5)
   == (insert (1 1 3 4) 5)
   => (1 1 3 4 5)
   @end lisp



Function: butlast lst n

butlast returns all but the last n elements of
lst.
Example:
(butlast '(1 2 3 4) 3)
   => (1)
(butlast '(1 2 3 4) 4)
   => ()



Function: nthcdr n lst

nthcdr takes n cdrs of lst and returns the
result.  Thus (nthcdr 3 lst) == (cdddr
lst)

Example:
(nthcdr 2 '(1 2 3 4))
   => (3 4)
(nthcdr 0 '(1 2 3 4))
   => (1 2 3 4)



Function: last lst n

last returns the last n elements of lst.  n
must be a non-negative integer.

Example:
(last '(foo bar baz bang) 2)
   => (baz bang)
(last '(1 2 3) 0)
   => 0


Destructive list operations

These procedures may mutate the list they operate on, but any such
mutation is undefined.


Procedure: nconc args

nconc destructively concatenates its arguments.  (Compare this
with append, which copies arguments rather than destroying them.)
Sometimes called append! (See section Rev2 Procedures).

Example:  You want to find the subsets of a set.  Here's the obvious way:

(define (subsets set)
  (if (null? set)
      '(())
      (append (mapcar (lambda (sub) (cons (car set) sub))
                      (subsets (cdr set)))
              (subsets (cdr set)))))

But that does way more consing than you need.  Instead, you could
replace the append with nconc, since you don't have any
need for all the intermediate results.

Example:
(define x '(a b c))
(define y '(d e f))
(nconc x y)
   => (a b c d e f)
x
   => (a b c d e f)


nconc is the same as append! in `sc2.scm'.


Procedure: nreverse lst

nreverse reverses the order of elements in lst by mutating
cdrs of the list.  Sometimes called reverse!.

Example:
(define foo '(a b c))
(nreverse foo)
   => (c b a)
foo
   => (a)


Some people have been confused about how to use nreverse,
thinking that it doesn't return a value.  It needs to be pointed out
that
(set! lst (nreverse lst))

is the proper usage, not
(nreverse lst)

The example should suffice to show why this is the case.


Procedure: delete elt lst


Procedure: delete-if pred lst


Procedure: delete-if-not pred lst

Destructive versions of remove remove-if, and
remove-if-not.

Example:
(define lst '(foo bar baz bang))
(delete 'foo lst)
   => (bar baz bang)
lst
   => (foo bar baz bang)

(define lst '(1 2 3 4 5 6 7 8 9))
(delete-if odd? lst)
   => (2 4 6 8)
lst
   => (1 2 4 6 8)


Some people have been confused about how to use delete,
delete-if, and delete-if, thinking that they dont' return
a value.  It needs to be pointed out that
(set! lst (delete el lst))

is the proper usage, not
(delete el lst)

The examples should suffice to show why this is the case.

Non-Common LISP functions


Function: and? . args

and? checks to see if all its arguments are true.  If they are,
and? returns #t, otherwise, #f.  (In contrast to
and, this is a function, so all arguments are always evaluated
and in an unspecified order.)

Example:
(and? 1 2 3)
   => #t
(and #f 1 2)
   => #f



Function: or? . args

or? checks to see if any of its arguments are true.  If any is
true, or? returns #t, and #f otherwise.  (To
or as and? is to and.)

Example:
(or? 1 2 #f)
   => #t
(or? #f #f #f)
   => #f



Function: atom? object

Returns #t if object is not a pair and #f if it is
pair.  (Called atom in Common LISP.)
(atom? 1)
   => #t
(atom? '(1 2))
   => #f
(atom? #(1 2))   ; dubious!
   => #t


Format

(require 'format)

Format Interface


Function: format destination format-string . arguments

An almost complete implementation of Common LISP format description
according to the CL reference book Common LISP from Guy L.
Steele, Digital Press.  Backward compatible to most of the available
Scheme format implementations.

Returns #t, #f or a string; has side effect of printing
according to format-string.  If destination is #t,
the output is to the current output port and #t is returned.  If
destination is #f, a formatted string is returned as the
result of the call.  NEW: If destination is a string,
destination is regarded as the format string; format-string is
then the first argument and the output is returned as a string. If
destination is a number, the output is to the current error port
if available by the implementation. Otherwise destination must be
an output port and #t is returned.

format-string must be a string.  In case of a formatting error
format returns #f and prints a message on the current output or
error port.  Characters are output as if the string were output by the
display function with the exception of those prefixed by a tilde
(~).  For a detailed description of the format-string syntax
please consult a Common LISP format reference manual.  For a test suite
to verify this format implementation load `formatst.scm'. Please
send bug reports to lutzeb@cs.tu-berlin.de.

Note: format is not reentrant, i.e. only one format-call
may be executed at a time.

Format Specification (Format version 3.0)

Please consult a Common LISP format reference manual for a detailed
description of the format string syntax.  For a demonstration of the
implemented directives see `formatst.scm'.

This implementation supports directive parameters and modifiers
(: and @ characters). Multiple parameters must be
separated by a comma (,).  Parameters can be numerical parameters
(positive or negative), character parameters (prefixed by a quote
character ('), variable parameters (v), number of rest
arguments parameter (#), empty and default parameters.  Directive
characters are case independent. The general form of a directive
is:

directive ::= ~{directive-parameter,}[:][@]directive-character

directive-parameter ::= [ [-|+]{0-9}+ | 'character | v | # ]

Implemented CL Format Control Directives

Documentation syntax: Uppercase characters represent the corresponding
control directive characters. Lowercase characters represent control
directive parameter descriptions.


~A
Any (print as display does).

~@A
left pad.
~mincol,colinc,minpad,padcharA
full padding.

~S
S-expression (print as write does).

~@S
left pad.
~mincol,colinc,minpad,padcharS
full padding.

~D
Decimal.

~@D
print number sign always.
~:D
print comma separated.
~mincol,padchar,commacharD
padding.

~X
Hexadecimal.

~@X
print number sign always.
~:X
print comma separated.
~mincol,padchar,commacharX
padding.

~O
Octal.

~@O
print number sign always.
~:O
print comma separated.
~mincol,padchar,commacharO
padding.

~B
Binary.

~@B
print number sign always.
~:B
print comma separated.
~mincol,padchar,commacharB
padding.

~nR
Radix n.

~n,mincol,padchar,commacharR
padding.

~@R
print a number as a Roman numeral.
~:R
print a number as an ordinal English number.
~:@R
print a number as a cardinal English number.
~P
Plural.

~@P
prints y and ies.
~:P
as ~P but jumps 1 argument backward.
~:@P
as ~@P but jumps 1 argument backward.

~C
Character.

~@C
prints a character as the reader can understand it (i.e. #\ prefixing).
~:C
prints a character as emacs does (eg. ^C for ASCII 03).

~F
Fixed-format floating-point (prints a flonum like mmm.nnn).

~width,digits,scale,overflowchar,padcharF
~@F
If the number is positive a plus sign is printed.

~E
Exponential floating-point (prints a flonum like mmm.nnnEee).

~width,digits,exponentdigits,scale,overflowchar,padchar,exponentcharE
~@E
If the number is positive a plus sign is printed.

~G
General floating-point (prints a flonum either fixed or exponential).

~width,digits,exponentdigits,scale,overflowchar,padchar,exponentcharG
~@G
If the number is positive a plus sign is printed.

~$
Dollars floating-point (prints a flonum in fixed with signs separated).

~digits,scale,width,padchar$
~@$
If the number is positive a plus sign is printed.
~:@$
A sign is always printed and appears before the padding.
~:$
The sign appears before the padding.

~%
Newline.

~n%
print n newlines.

~&
print newline if not at the beginning of the output line.

~n&
prints ~& and then n-1 newlines.

~|
Page Separator.

~n|
print n page separators.

~~
Tilde.

~n~
print n tildes.

~<newline>
Continuation Line.

~:<newline>
newline is ignored, white space left.
~@<newline>
newline is left, white space ignored.

~T
Tabulation.

~@T
relative tabulation.
~colnum,colincT
full tabulation.

~?
Indirection (expects indirect arguments as a list).

~@?
extracts indirect arguments from format arguments.

~(str~)
Case conversion (converts by string-downcase).

~:(str~)
converts by string-capitalize.
~@(str~)
converts by string-capitalize-first.
~:@(str~)
converts by string-upcase.

~*
Argument Jumping (jumps 1 argument forward).

~n*
jumps n arguments forward.
~:*
jumps 1 argument backward.
~n:*
jumps n arguments backward.
~@*
jumps to the 0th argument.
~n@*
jumps to the nth argument (beginning from 0)

~[str0~;str1~;...~;strn~]
Conditional Expression (numerical clause conditional).

~n[
take argument from n.
~@[
true test conditional.
~:[
if-else-then conditional.
~;
clause separator.
~:;
default clause follows.

~{str~}
Iteration (args come from the next argument (a list)).

~n{
at most n iterations.
~:{
args from next arg (a list of lists).
~@{
args from the rest of arguments.
~:@{
args from the rest args (lists).

~^
Up and out.

~n^
aborts if n = 0
~n,m^
aborts if n = m
~n,m,k^
aborts if n <= m <= k



Not Implemented CL Format Control Directives


~:A
print #f as an empty list (see below).
~:S
print #f as an empty list (see below).
~<~>
Justification.
~:^
(sorry I don't understand its semantics completely)


Extended, Replaced and Additional Control Directives


~mincol,padchar,commachar,commawidthD
~mincol,padchar,commachar,commawidthX
~mincol,padchar,commachar,commawidthO
~mincol,padchar,commachar,commawidthB
~n,mincol,padchar,commachar,commawidthR
commawidth is the number of characters between two comma characters.



~I
print a R4RS complex number as ~F~@Fi with passed parameters for
~F.
~Y
Pretty print formatting of an argument for scheme code lists.
~K
Same as ~?.
~!
Flushes the output if format destination is a port.
~_
Print a #\space character

~n_
print n #\space characters.

~/
Print a #\tab character

~n/
print n #\tab characters.

~nC
Takes n as an integer representation for a character. No arguments
are consumed. n is converted to a character by
integer->char.  n must be a positive decimal number.
~:S
Print out readproof.  Prints out internal objects represented as
#<...> as strings "#<...>" so that the format output can always
be processed by read.
~:A
Print out readproof.  Prints out internal objects represented as
#<...> as strings "#<...>" so that the format output can always
be processed by read.
~Q
Prints information and a copyright notice on the format implementation.

~:Q
prints format version.

~F, ~E, ~G, ~$
may also print number strings, i.e. passing a number as a string and
format it accordingly.


Configuration Variables

Format has some configuration variables at the beginning of
`format.scm' to suit the systems and users needs. There should be
no modification necessary for the configuration that comes with SLIB.
If modification is desired the variable should be set after the format
code is loaded. Format detects automatically if the running scheme
system implements floating point numbers and complex numbers.



format:symbol-case-conv
Symbols are converted by symbol->string so the case type of the
printed symbols is implementation dependent.
format:symbol-case-conv is a one arg closure which is either
#f (no conversion), string-upcase, string-downcase
or string-capitalize. (default #f)

format:iobj-case-conv
As format:symbol-case-conv but applies for the representation of
implementation internal objects. (default #f)

format:expch
The character prefixing the exponent value in ~E printing. (default
#\E)



Compatibility With Other Format Implementations


SLIB format 2.x:
See `format.doc'.

SLIB format 1.4:
Downward compatible except for padding support and ~A, ~S,
~P, ~X uppercase printing.  SLIB format 1.4 uses C-style
printf padding support which is completely replaced by the CL
format padding style.

MIT C-Scheme 7.1:
Downward compatible except for ~, which is not documented
(ignores all characters inside the format string up to a newline
character).  (7.1 implements ~a, ~s,
~newline, ~~, ~%, numerical and variable
parameters and :/@ modifiers in the CL sense).

Elk 1.5/2.0:
Downward compatible except for ~A and ~S which print in
uppercase.  (Elk implements ~a, ~s, ~~, and
~% (no directive parameters or modifiers)).

Scheme->C 01nov91:
Downward compatible except for an optional destination parameter: S2C
accepts a format call without a destination which returns a formatted
string. This is equivalent to a #f destination in S2C. (S2C implements
~a, ~s, ~c, ~%, and ~~ (no directive
parameters or modifiers)).



This implementation of format is solely useful in the SLIB context
because it requires other components provided by SLIB.

Generic-Write

(require 'generic-write)

generic-write is a procedure that transforms a Scheme data value
(or Scheme program expression) into its textual representation and
prints it.  The interface to the procedure is sufficiently general to
easily implement other useful formatting procedures such as pretty
printing, output to a string and truncated output.


Procedure: generic-write obj display? width output


obj
Scheme data value to transform.
display?
Boolean, controls whether characters and strings are quoted.
width
Extended boolean, selects format:

#f
single line format
integer > 0
pretty-print (value = max nb of chars per line)

output
Procedure of 1 argument of string type, called repeatedly with
successive substrings of the textual representation.  This procedure can
return #f to stop the transformation.


The value returned by generic-write is undefined.

Examples:
(write obj) == (generic-write obj #f #f display-string)
(display obj) == (generic-write obj #t #f display-string)

where
display-string ==
(lambda (s) (for-each write-char (string->list s)) #t)


Line I/O

(require 'line-i/o)


Function: read-line


Function: read-line port

Returns a string of the characters up to, but not including a newline or
end of file, updating port to point to the character following the
newline.  If no characters are available, an end of file object is
returned.  port may be omitted, in which case it defaults to the
value returned by current-input-port.


Function: read-line! string


Function: read-line! string port

Fills string with characters up to, but not including a newline or
end of file, updating the port to point to the last character read or
following the newline if it was read.  If no characters are available,
an end of file object is returned.  If a newline or end of file was
found, the number of characters read is returned.  Otherwise, #f
is returned.  port may be omitted, in which case it defaults to
the value returned by current-input-port.


write-line: string


write-line: string port

Writes string followed by a newline to the given port and returns
an unspecified value.  Port may be omited, in which case it defaults to
the value returned by current-input-port.

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.

For all of these procedure all arguments should be exact non-negative
integers such that k1 > k2 and k1 > k3.  The returned value will be an
exact non-negative integer less than k1.  If all the arguments are
fixnums the computation will use only fixnums.


Function: modular:invert k1 k2

Returns an integer n such that 1 = (n * k2) mod k1.  If k2 has no
inverse mod k1 an error is signaled.


Function: modular:negate k1 k2

Returns (-k2) mod k1.


Function: modular:+ k1 k2 k3

Returns (k2 + k3) mod k1.


Function: modular:- k1 k2 k3

Returns (k2 - k3) mod k1.


Function: modular:* k1 k2 k3

Returns (k2 * k3) mod k1.


Function: modular:expt k1 k2 k3

Returns (k2 ^ k3) mod k1.

Multi-Processing

(require 'process)


Procedure: add-process! proc

Adds proc, which must be a procedure (or continuation) capable of
accepting accepting one argument, to the process:queue.  The
value returned is unspecified.  The argument to proc should be
ignored.  If proc returns, the process is killed.


Procedure: process:schedule!

Saves the current process on process:queue and runs the next
process from process:queue.  The value returned is
unspecified.


Procedure: kill-process!

Kills the current process and runs the next process from
process:queue.  If there are no more processes on
process:queue, (slib:exit) is called (See section System).

Object-To-String

(require 'object->string)


Function: object->string obj

Returns the textual representation of obj as a string.

Plotting on Character Devices

(require 'charplot)

The plotting procedure is made available through the use of the
charplot package.  charplot is loaded by inserting
(require 'charplot) before the code that uses this
procedure.


Variable: charplot:height

The number of rows to make the plot vertically.


Variable: charplot:width

The number of columns to make the plot horizontally.


Procedure: plot! coords x-label y-label

coords is a list of pairs of x and y coordinates.  x-label
and y-label are strings with which to label the x and y
axes.

Example:
(require 'charplot)
(set! charplot:height 19)
(set! charplot:width 45)

(define (make-points n)
  (if (zero? n)
      '()
      (cons (cons (/ n 6) (sin (/ n 6))) (make-points (1- n)))))

(plot! (make-points 37) "x" "Sin(x)")
-|
  Sin(x)   ______________________________________________
      1.25|-                                             |
          |                                              |
         1|-       ****                                  |
          |      **    **                                |
  750.0e-3|-    *        *                               |
          |    *          *                              |
  500.0e-3|-  *            *                             |
          |  *                                           |
  250.0e-3|-                *                            |
          | *                *                           |
         0|-------------------*--------------------------|
          |                                     *        |
 -250.0e-3|-                   *               *         |
          |                     *             *          |
 -500.0e-3|-                     *                       |
          |                       *          *           |
 -750.0e-3|-                       *        *            |
          |                         **    **             |
        -1|-                          ****               |
          |____________:_____._____:_____._____:_________|
        x              2           4      


Pretty-Print

(require 'pretty-print)


Procedure: pretty-print obj


Procedure: pretty-print obj port


pretty-prints obj on port.  If port is not
specified, current-output-port is used.

Example:
(pretty-print '((1 2 3 4 5) (6 7 8 9 10) (11 12 13 14 15)
                (16 17 18 19 20) (21 22 23 24 25)))
   -| ((1 2 3 4 5)
   -|  (6 7 8 9 10)
   -|  (11 12 13 14 15)
   -|  (16 17 18 19 20)
   -|  (21 22 23 24 25))


(require 'pprint-file)


Procedure: pprint-file infile


Procedure: pprint-file infile outfile

Pretty-prints all the code in infile.  If outfile is
specified, the output goes to outfile, otherwise it goes to
(current-output-port).


Function: pprint-filter-file infile proc outfile


Function: pprint-filter-file infile proc

infile is a port or a string naming an existing file.  Scheme
source code expressions and definitions are read from the port (or file)
and proc is applied to them sequentially.

outfile is a port or a string.  If no outfile is specified
then current-output-port is assumed.  These expanded expressions
are then pretty-printed to this port.

Whitepsace and comments (introduced by ;) which are not part of
scheme expressions are reproduced in the output.  This procedure does
not affect the values returned by current-input-port and
current-output-port.

pprint-filter-file can be used to pre-compile macro-expansion and
thus can reduce loading time.  The following will write into
`exp-code.scm' the result of expanding all defmacros in
`code.scm'.
(require 'pprint-file)
(require 'defmacroexpand)
(defmacro:load "my-macros.scm")
(pprint-filter-file "code.scm" defmacro:expand* "exp-code.scm")


Prime Factorization

(require 'prime)

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.


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

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

Sorting

(require 'sort)

Many Scheme systems provide some kind of sorting functions.  They do
not, however, always provide the same sorting functions, and
those that I have had the opportunity to test provided inefficient ones
(a common blunder is to use quicksort which does not perform well).

Because sort and sort! are not in the standard, there is
very little agreement about what these functions look like.  For
example, Dybvig says that Chez Scheme provides
(merge predicate list1 list2)
(merge! predicate list1 list2)
(sort predicate list)
(sort! predicate list)

while MIT Scheme 7.1, following Common LISP, offers unstable
(sort list predicate)

TI PC Scheme offers
(sort! list/vector predicate?)

and Elk offers
(sort list/vector predicate?)
(sort! list/vector predicate?)


Here is a comprehensive catalogue of the variations I have found.



Both sort and sort! may be provided.

sort may be provided without sort!.

sort! may be provided without sort.

Neither may be provided.

The sequence argument may be either a list or a vector.

The sequence argument may only be a list.

The sequence argument may only be a vector.

The comparison function may be expected to behave like <.

The comparison function may be expected to behave like <=.

The interface may be (sort predicate? sequence).

The interface may be (sort sequence predicate?).

The interface may be (sort sequence &optional (predicate? <)).

The sort may be stable.

The sort may be unstable.


All of this variation really does not help anybody.  A nice simple merge
sort is both stable and fast (quite a lot faster than `quick' sort).

I am providing this source code with no restrictions at all on its use
(but please retain D.H.D.Warren's credit for the original idea).  You
may have to rename some of these functions in order to use them in a
system which already provides incompatible or inferior sorts.  For each
of the functions, only the top-level define needs to be edited to do
that.

I could have given these functions names which would not clash with any
Scheme that I know of, but I would like to encourage implementors to
converge on a single interface, and this may serve as a hint.  The
argument order for all functions has been chosen to be as close to
Common LISP as made sense, in order to avoid NIH-itis.

Each of the five functions has a required last parameter which is
a comparison function.  A comparison function f is a function of
2 arguments which acts like <.  For example,

(not (f x x))
(and (f x y) (f y z)) == (f x z)


The standard functions <, >, char<?, char>?,
char-ci<?, char-ci>?, string<?, string>?,
string-ci<?, and string-ci>? are suitable for use as
comparison functions.  Think of (less? x y) as saying when
x must not precede y.


Function: sorted? sequence less?

Returns #t when the sequence argument is in non-decreasing order
according to less? (that is, there is no adjacent pair ... x
y ... for which (less? y x)).

Returns #f when the sequence contains at least one out-of-order
pair.  It is an error if the sequence is neither a list nor a vector.


Function: merge list1 list2 less?

This merges two lists, producing a completely new list as result.  I
gave serious consideration to producing a Common-LISP-compatible
version.  However, Common LISP's sort is our sort! (well,
in fact Common LISP's stable-sort is our sort!, merge sort
is fast as well as stable!) so adapting CL code to Scheme takes a
bit of work anyway.  I did, however, appeal to CL to determine the
order of the arguments.


Procedure: merge! list1 list2 less?

Merges two lists, re-using the pairs of list1 and list2 to
build the result.  If the code is compiled, and less? constructs
no new pairs, no pairs at all will be allocated.  The first pair of the
result will be either the first pair of list1 or the first pair of
list2, but you can't predict which.

The code of merge and merge! could have been quite a bit
simpler, but they have been coded to reduce the amount of work done per
iteration.  (For example, we only have one null? test per
iteration.)


Function: sort sequence less?

Accepts either a list or a vector, and returns a new sequence which is
sorted.  The new sequence is the same type as the input.  Always
(sorted? (sort sequence less?) less?).  The original sequence is
not altered in any way.  The new sequence shares its elements
with the old one; no elements are copied.


Procedure: sort! sequence less?

Returns its sorted result in the original boxes.  If the original
sequence is a list, no new storage is allocated at all.  If the original
sequence is a vector, the sorted elements are put back in the same
vector.

Some people have been confused about how to use sort!, thinking
that it doesn't return a value.  It needs to be pointed out that
(set! slist (sort! slist <))

is the proper usage, not
(sort! slist <)


Note that these functions do not accept a CL-style `:key'
argument.  A simple device for obtaining the same expressiveness is to
define
(define (keyed less? key)
  (lambda (x y) (less? (key x) (key y))))

and then, when you would have written
(sort a-sequence #'my-less :key #'my-key)

in Common LISP, just write
(sort! a-sequence (keyed my-less? my-key))

in Scheme.

Standard I/O

(require 'stdio)


Procedure: printf format . args


Procedure: fprintf port format . args


Procedure: sprintf str format . args


Note: Floating-point output is not handled yet.


Variable: stdin

Defined to be (current-input-port).


Variable: stdout

Defined to be (current-output-port).


Variable: stderr

Defined to be (current-error-port).


Function: scanf format . args


Function: fscanf port format . args


Function: sscanf str format . args


Each function reads characters, interprets them according to the control
string format argument, and returns a list of the items specified.
args are ignored; they are allowed for compatability with the C
function of the same name.  The control string contains conversion
specifications and other characters used to direct interpretation of
input sequences.  The control string contains:


White-space characters (blanks, tabs, newlines, or formfeeds)
that cause input to be read up to the next non-white-space character
(except in cases described below).

An ordinary character (not `%') that must match the next
character of the input stream.

Conversion specifications, consisting of the character `%', an
optional assignment suppressing character `*', an optional
numerical maximum-field width, an optional `l' (ell), `h' or
`L' which is ignored, and a conversion code.



A conversion specification directs the conversion of the next input
field.  The result of a conversion specification is returned in the
position of the corresponding argument points, unless `*'
indicates assignment suppression.  Assignment suppression provides a way
to describe an input field to be skipped.  An input field is defined as
a string of non-space characters; it extends to the next inappropriate
character or until the field width, if specified, is exhausted.  For all
descriptors except
`c', white space leading an input field is ignored.

The conversion code indicates the interpretation of the input field; For
a suppressed field, no value is returned.  The following conversion
codes are legal:



`%'
A single % is expected in the input at this point; no value is returned.

`d'
A decimal integer is expected.

`o'
An octal integer is expected.

`x'
A hexadecimal integer is expected.

`f'
A floating-point number is expected.  The input format for
floating-point numbers is an optionally signed string of digits,
possibly containing a radix character, followed by an optional exponent
field consisting of an `E' or an `e', followed by an optional
`+', `-', or space, followed by an integer.

`c'
A character is expected.  The normal skip-over-white-space is suppressed
in this case; to read the next non-space character, use `%1s'.  If
a field width is given, a string is returned; the indicated number of
characters is read.

`s'
`S'
A character string is expected The input field is terminated by a
white-space character.  scanf cannot read a null string.



The `l', `L' and `h' modifiers are ignored.

The scanf functions terminate their conversions at end-of-file,
at the end of the control string, or when an input character conflicts
with the control string.  In the latter case, the offending character is
left unread in the input stream.

String-Case

(require 'string-case)


Procedure: string-upcase str


Procedure: string-downcase str


Procedure: string-capitalize str

The obvious string conversion routines.  These are non-destructive.


Function: string-upcase! str


Function: string-downcase! str


Function: string-captialize! str

The destructive versions of the functions above.

String Ports

(require 'string-port)


Procedure: call-with-output-string proc

proc must be a procedure of one argument.  This procedure calls
proc with one argument: a (newly created) output port.  When the
function returns, the string composed of the characters written into the
port is returned.


Procedure: call-with-input-string string proc

proc must be a procedure of one argument.  This procedure calls
proc with one argument: an (newly created) input port from which
string's contents may be read.  When proc returns, the port
is closed and the value yielded by the procedure proc is
returned.

Tektronix Graphics Support

Note: The Tektronix graphics support files need more work, and
are not complete.

Tektronix 4000 Series Graphics

The Tektronix 4000 series graphics protocol gives the user a 1024 by
1024 square drawing area.  The origin is in the lower left corner of the
screen.  Increasing y is up and increasing x is to the right.

The graphics control codes are sent over the current-output-port and can
be mixed with regular text and ANSI or other terminal control sequences.


Procedure: tek40:init



Procedure: tek40:graphics



Procedure: tek40:text



Procedure: tek40:linetype linetype



Procedure: tek40:move x y



Procedure: tek40:draw x y



Procedure: tek40:put-text x y str



Procedure: tek40:reset


Tektronix 4100 Series Graphics

The graphics control codes are sent over the current-output-port and can
be mixed with regular text and ANSI or other terminal control sequences.


Procedure: tek41:init



Procedure: tek41:reset



Procedure: tek41:graphics



Procedure: tek41:move x y



Procedure: tek41:draw x y



Procedure: tek41:point x y number



Procedure: tek41:encode-x-y x y



Procedure: tek41:encode-int number


Tree operations

These are operations that treat lists a representations of trees.


Function: subst new old tree


Function: substq new old tree


Function: substv new old tree

subst makes a copy of tree, substituting new for
every subtree or leaf of tree which is equal? to old
and returns a modified tree.  The original tree is unchanged, but
may share parts with the result.

substq and substv are similar, but test against old
using eq? and eqv? respectively.

Examples:
(substq 'tempest 'hurricane '(shakespeare wrote (the hurricane)))
   => (shakespeare wrote (the tempest))
(substq 'foo '() '(shakespeare wrote (twelfth night)))
   => (shakespeare wrote (twelfth night . foo) . foo)
(subst '(a . cons) '(old . pair)
       '((old . spice) ((old . shoes) old . pair) (old . pair)))
   => ((old . spice) ((old . shoes) a . cons) (a . cons))



Function: copy-tree tree

Makes a copy of the nested list structure tree using new pairs and
returns it.  All levels are copied, so that none of the pairs in the
tree are eq? to the original ones -- only the leaves are.

Example:
(define bar '(bar))
(copy-list (list bar 'foo))
   => ((bar) foo)
(eq? bar (car (copy-list (list bar 'foo))))
   => #f


Go to the previous, next section.