#t if the obj is an array, and #f if not.
When constructing an array, bound is either an inclusive range of indices expressed as a two element list, or an upper bound expressed as a single integer. So
(make-array 'foo 3 3) == (make-array 'foo '(0 2) '(0 2))
make-shared-array can be used to create shared subarrays of other
arrays. The mapper is a function that translates coordinates in
the new array into coordinates in the old array. A mapper must be
linear, and its range must stay within the bounds of the old array, but
it can be otherwise arbitrary. A simple example:
(define fred (make-array #f 8 8))
(define freds-diagonal
(make-shared-array fred (lambda (i) (list i i)) 8))
(array-set! freds-diagonal 'foo 3)
(array-ref fred 3 3)
=> FOO
(define freds-center
(make-shared-array fred (lambda (i j) (list (+ 3 i) (+ 3 j)))
2 2))
(array-ref freds-center 0 0)
=> FOO
array-shape returns a list of inclusive bounds. So:
(array-shape (make-array 'foo 3 5)) => ((0 2) (0 4))
array-dimensions is similar to array-shape but replaces
elements with a 0 minimum with one greater than the maximum. So:
(array-dimensions (make-array 'foo 3 5)) => (3 5)
#t if its arguments would be acceptable to
array-ref.
(index1, index2) element
in array.
The functions are just fast versions of array-ref and
array-set! that take a fixed number of arguments, and perform no
bounds checking.
If you comment out the bounds checking code, this is about as efficient as you could ask for without help from the compiler.
An exercise left to the reader: implement the rest of APL.
One can implement array-indexes as
(define (array-indexes array)
(let ((ra (apply make-array #f (array-shape array))))
(array-index-map! ra (lambda x x))
ra))
Another example:
(define (apl:index-generator n)
(let ((v (make-uniform-vector n 1)))
(array-index-map! v (lambda (i) i))
v))
Alist functions provide utilities for treating a list of key-value pairs as an associative database. These functions take an equality predicate, pred, as an argument. This predicate should be repeatable, symmetric, and transitive.
Alist functions can be used with a secondary index method such as hash tables for improved performance.
assq, assv, or
assoc) corresponding to pred. The returned function
returns a key-value pair whose key is pred-equal to its first
argument or #f if no key in the alist is pred-equal to the
first argument.
#f if
key does not appear in alist.
(define put (alist-associator string-ci=?)) (define alist '()) (set! alist (put alist "Foo" 9))
(define rem (alist-remover string-ci=?)) (set! alist (rem alist "foo"))
(require 'byte)
Some algorithms are expressed in terms of arrays of small integers. Using Scheme strings to implement these arrays is not portable vis-a-vis the correspondence between integers and characters and non-ascii character sets. These functions abstract the notion of a byte.
byte-ref returns
byte k of bytes using zero-origin indexing.
Byte-set! stores byte in element k
of bytes
and returns an unspecified value.
Make-bytes returns a newly allocated byte-array of
length k. If byte is given, then all elements of the
byte-array are initialized to byte, otherwise the contents of the
byte-array are unspecified.
Writes the byte byte (not an external representation of the
byte) to the given port and returns an unspecified value. The
port argument may be omitted, in which case it defaults to the value
returned by current-output-port.
Returns the next byte available from the input port, updating
the port to point to the following byte. If no more bytes
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.
Returns a newly allocated byte-array composed of the arguments.
Bytes->list returns a newly allocated list of the
bytes that make up the given byte-array. List->bytes
returns a newly allocated byte-array formed from the small integers in
the list bytes. Bytes->list and list->bytes are
inverses so far as equal? is concerned.
Routines for managing collections. Collections are aggregate data structures supporting iteration over their elements, similar to the Dylan(TM) language, but with a different interface. They have elements indexed by corresponding keys, although the keys may be implicit (as with lists).
New types of collections may be defined as YASOS objects (See section Yasos). They must support the following operations:
(collection? self) (always returns #t);
(size self) returns the number of elements in the collection;
(print self port) is a specialized print operation
for the collection which prints a suitable representation on the given
port or returns it as a string if port is #t;
(gen-elts self) returns a thunk which on successive
invocations yields elements of self in order or gives an error if
it is invoked more than (size self) times;
(gen-keys self) is like gen-elts, but yields the
collection's keys in order.
They might support specialized for-each-key and
for-each-elt operations.
#t to collection?.
do-elts is used when only side-effects of proc are of
interest and its return value is unspecified. map-elts returns a
collection (actually a vector) of the results of the applications of
proc.
Example:
(map-elts + (list 1 2 3) (vector 1 2 3)) => #(2 4 6)
map-elts and do-elts, but each
iteration is over the collections' keys rather than their
elements.
Example:
(map-keys + (list 1 2 3) (vector 1 2 3)) => #(0 2 4)
do-keys and do-elts but only for a single
collection; they are potentially more efficient.
comlist:reduce-init
(See section Lists as sequences) to collections which will shadow the
list-based version if (require 'collect) follows
(require 'common-list-functions) (See section Common List Functions).
Examples:
(reduce + 0 (vector 1 2 3)) => 6 (reduce union '() '((a b c) (b c d) (d a))) => (c b d a).
some (See section Lists as sequences) to collections.
Example:
(any? odd? (list 2 3 4 5)) => #t
every (See section Lists as sequences) to collections.
Example:
(every? collection? '((1 2) #(1 2))) => #t
#t iff there are no elements in collection.
(empty? collection) == (zero? (size collection))
(setter list-ref) doesn't work properly for element 0 of a
list.
Here is a sample collection: simple-table which is also a
table.
(define-predicate TABLE?)
(define-operation (LOOKUP table key failure-object))
(define-operation (ASSOCIATE! table key value)) ;; returns key
(define-operation (REMOVE! table key)) ;; returns value
(define (MAKE-SIMPLE-TABLE)
(let ( (table (list)) )
(object
;; table behaviors
((TABLE? self) #t)
((SIZE self) (size table))
((PRINT self port) (format port "#<SIMPLE-TABLE>"))
((LOOKUP self key failure-object)
(cond
((assq key table) => cdr)
(else failure-object)
))
((ASSOCIATE! self key value)
(cond
((assq key table)
=> (lambda (bucket) (set-cdr! bucket value) key))
(else
(set! table (cons (cons key value) table))
key)
))
((REMOVE! self key);; returns old value
(cond
((null? table) (slib:error "TABLE:REMOVE! Key not found: " key))
((eq? key (caar table))
(let ( (value (cdar table)) )
(set! table (cdr table))
value)
)
(else
(let loop ( (last table) (this (cdr table)) )
(cond
((null? this)
(slib:error "TABLE:REMOVE! Key not found: " key))
((eq? key (caar this))
(let ( (value (cdar this)) )
(set-cdr! last (cdr this))
value)
)
(else
(loop (cdr last) (cdr this)))
) ) )
))
;; collection behaviors
((COLLECTION? self) #t)
((GEN-KEYS self) (collect:list-gen-elts (map car table)))
((GEN-ELTS self) (collect:list-gen-elts (map cdr table)))
((FOR-EACH-KEY self proc)
(for-each (lambda (bucket) (proc (car bucket))) table)
)
((FOR-EACH-ELT self proc)
(for-each (lambda (bucket) (proc (cdr bucket))) table)
)
) ) )
dynamic? satisfies any of the other standard type
predicates.
The dynamic-bind macro is not implemented.
hashq, hashv, or
hash) corresponding to the equality predicate pred.
pred should be eq?, eqv?, equal?, =,
char=?, char-ci=?, string=?, or
string-ci=?.A hash table is a vector of association lists.
Hash table functions provide utilities for an associative database.
These functions take an equality predicate, pred, as an argument.
pred should be eq?, eqv?, equal?, =,
char=?, char-ci=?, string=?, or
string-ci=?.
#f if no key in hashtab is pred-equal to
the first argument.
hashtab and key, which
returns the value associated with key in hashtab or
#f if key does not appear in hashtab.
These hashing functions are for use in quickly classifying objects. Hash tables use these functions.
For hashq, (eq? obj1 obj2) implies (= (hashq obj1 k)
(hashq obj2)).
For hashv, (eqv? obj1 obj2) implies (= (hashv obj1 k)
(hashv obj2)).
For hash, (equal? obj1 obj2) implies (= (hash obj1 k)
(hash obj2)).
hash, hashv, and hashq return in time bounded by a
constant. Notice that items having the same hash implies the
items have the same hashv implies the items have the same
hashq.
max-coordinate is the maximum coordinate (a positive integer) of a population of points. The returned procedures is a function that takes the x and y coordinates of a point, (non-negative integers) and returns an integer corresponding to the relative position of that point along a Sierpinski curve. (You can think of this as computing a (pseudo-) inverse of the Sierpinski spacefilling curve.)
Example use: Make an indexer (hash-function) for integer points lying in square of integer grid points [0,99]x[0,99]:
(define space-key (make-sierpinski-indexer 100))
Now let's compute the index of some points:
(space-key 24 78) => 9206 (space-key 23 80) => 9172
Note that locations (24, 78) and (23, 80) are near in index and therefore, because the Sierpinski spacefilling curve is continuous, we know they must also be near in the plane. Nearness in the plane does not, however, necessarily correspond to nearness in index, although it tends to be so.
Example applications:
Soundex was a classic algorithm used for manual filing of personal records before the advent of computers. It performs adequately for English names but has trouble with other nationalities.
See Knuth, Vol. 3 Sorting and searching, pp 391--2
To manage unusual inputs, soundex omits all non-alphabetic
characters. Consequently, in this implementation:
(soundex <string of blanks>) => "" (soundex "") => ""
Examples from Knuth:
(map soundex '("Euler" "Gauss" "Hilbert" "Knuth"
"Lloyd" "Lukasiewicz"))
=> ("E460" "G200" "H416" "K530" "L300" "L222")
(map soundex '("Ellery" "Ghosh" "Heilbronn" "Kant"
"Ladd" "Lissajous"))
=> ("E460" "G200" "H416" "K530" "L300" "L222")
Some cases in which the algorithm fails (Knuth):
(map soundex '("Rogers" "Rodgers")) => ("R262" "R326")
(map soundex '("Sinclair" "St. Clair")) => ("S524" "S324")
(map soundex '("Tchebysheff" "Chebyshev")) => ("T212" "C121")
make-heap. If there are no items in
heap, an error is signaled.The algorithm for priority queues was taken from Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest. 1989 MIT Press.
A queue is a list where elements can be added to both the front and rear, and removed from the front (i.e., they are what are often called dequeues). A queue may also be used like a stack.
#t if obj is a queue.
#t if the queue q is empty.
All of the following functions raise an error if the queue q is empty.
queue-pop! is used to suggest that the queue is being
used like a stack.The Record package provides a facility for user to define their own record data types.
make-record-type that created the type represented by rtd;
if the field-names argument is provided, it is an error if it
contains any duplicates or any symbols not in the default list.
make-record-type
that created the type represented by rtd.
make-record-type that created the type represented by
rtd.
In May of 1996, as a product of discussion on the rrrs-authors
mailing list, I rewrote `record.scm' to portably implement type
disjointness for record data types.
As long as an implementation's procedures are opaque and the
record code is loaded before other programs, this will give
disjoint record types which are unforgeable and incorruptible by R4RS
procedures.
As a consequence, the procedures record?,
record-type-descriptor, record-type-name.and
record-type-field-names are no longer supported.
(require 'struct) (uses defmacros)
defmacros which implement records from the book
Essentials of Programming Languages by Daniel P. Friedman, M.
Wand and C.T. Haynes. Copyright 1992 Jeff Alexander, Shinnder Lee, and
Lewis Patterson
Matthew McDonald <mafm@cs.uwa.edu.au> added field setters.
Here is an example of its use.
(define-record term (operator left right)) => #<unspecified> (define foo (make-term 'plus 1 2)) => foo (term->left foo) => 1 (set-term-left! foo 2345) => #<unspecified> (term->left foo) => 2345
((lambda (var1 var ...) body) (tag->var1 exp) (tag->var2 exp) ...)
Anything that doesn't fall neatly into any of the other categories winds up here.
(require 'common-list-functions)
The procedures below follow the Common LISP equivalents apart from optional arguments in some cases.
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)
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)
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
eqv? is used to test for membership by procedures which treat
lists as sets.
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)
union returns the combination of l1 and l2.
Duplicates between l1 and l2 are culled. Duplicates within
l1 or within l2 may or may not be removed.
Example:
(union '(1 2 3 4) '(5 6 7 8)) => (4 3 2 1 5 6 7 8) (union '(1 2 3 4) '(3 4 5 6)) => (2 1 3 4 5 6)
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)) => ()
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)) => ()
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)
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
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
notany is analogous to some but returns #t if no
application of pred returns #t or #f as soon as any
one does.
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
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
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)
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)
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)
#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
The procedure remove-duplicates uses member (rather than
memv).
equal?.
Example:
(remove-duplicates '(1 2 3 4)) => (4 3 2 1) (remove-duplicates '(2 4 3 4)) => (3 4 2)
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
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)))
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
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
butlast returns all but the last n elements of
lst.
Example:
(butlast '(a b c d) 3) => (a) (butlast '(a b c d) 4) => ()
last and butlast split a list into two parts when given
identical arugments.
(last '(a b c d e) 2) => (d e) (butlast '(a b c d e) 2) => (a b c)
nthcdr takes n cdrs of lst and returns the
result. Thus (nthcdr 3 lst) == (cdddr
lst)
Example:
(nthcdr 2 '(a b c d)) => (c d) (nthcdr 0 '(a b c d)) => (a b c d)
butnthcdr returns all but the nthcdr n elements of
lst.
Example:
(butnthcdr 3 '(a b c d)) => (a b c) (butnthcdr 4 '(a b c d)) => ()
nthcdr and butnthcdr split a list into two parts when
given identical arugments.
(nthcdr 2 '(a b c d e)) => (c d e) (butnthcdr 2 '(a b c d e)) => (a b)
These procedures may mutate the list they operate on, but any such mutation is undefined.
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'.
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.
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.
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
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
#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
char, number,
string, symbol, list, or vector to
result-type (which must be one of these symbols).
These are operations that treat lists a representations of trees.
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))
eq? to the original ones -- only the leaves are.
Example:
(define bar '(bar)) (copy-tree (list bar 'foo)) => ((bar) foo) (eq? bar (car (copy-tree (list bar 'foo)))) => #f
The `chap:' functions deal with strings which are ordered like chapter numbers (or letters) in a book. Each section of the string consists of consecutive numeric or consecutive aphabetic characters of like case.
string<? than the corresponding non-matching run of characters of
string2.
(chap:string<? "a.9" "a.10") => #t
(chap:string<? "4c" "4aa") => #t
(chap:string<? "Revised^{3.99}" "Revised^{4}") => #t
(string-append string "0") is returnd. The argument to
chap:next-string will always be chap:string<? than the result.
(chap:next-string "a.9") => "a.10"
(chap:next-string "4c") => "4d"
(chap:next-string "4z") => "4aa"
(chap:next-string "Revised^{4}") => "Revised^{5}"
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.
sort and sort! may be provided.
sort may be provided without sort!.
sort! may be provided without sort.
<.
<=.
(sort predicate? sequence).
(sort sequence predicate?).
(sort sequence &optional (predicate? <)).
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.
#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.
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.
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.)
(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.
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.
(require 'topological-sort) or (require 'tsort)
The algorithm is inspired by Cormen, Leiserson and Rivest (1990) Introduction to Algorithms, chapter 23.
eq?, eqv?, equal?, =,
char=?, char-ci=?, string=?, or string-ci=?.
Sort the directed acyclic graph dag so that for every edge from vertex u to v, u will come before v in the resulting list of vertices.
Time complexity: O (|V| + |E|)
Example (from Cormen):
Prof. Bumstead topologically sorts his clothing when getting dressed. The first argument to `tsort' describes which garments he needs to put on before others. (For example, Prof Bumstead needs to put on his shirt before he puts on his tie or his belt.) `tsort' gives the correct order of dressing:
(require 'tsort)
(tsort '((shirt tie belt)
(tie jacket)
(belt jacket)
(watch)
(pants shoes belt)
(undershorts pants shoes)
(socks shoes))
eq?)
=>
(socks undershorts pants shoes watch shirt belt tie jacket)
read.
#f if the string does not contain a
character char.
#f if the string does not contain a
character char.
substring? returns the index of the first
character of the first substring of string that is equal to
pattern; or #f if string does not contain
pattern.
(substring? "rat" "pirate") => 2 (substring? "rat" "outrage") => #f (substring? "" any-string) => 0
When the str is found, find-string-from-port? returns the
number of characters it has read from the port, and the port is set to
read the first char after that (that is, after the str) The
function returns #f when the str isn't found.
find-string-from-port? reads the port strictly
sequentially, and does not perform any buffering. So
find-string-from-port? can be used even if the in-port is
open to a pipe or other communication channel.
current-input-port.
#f is returned. The port argument may be
omitted, in which case it defaults to the value returned by
current-input-port.
current-input-port.
current-output-port.
This module implements asynchronous (non-polled) time-sliced
multi-processing in the SCM Scheme implementation using procedures
alarm and alarm-interrupt.
Until this is ported to another implementation, consider it an example
of writing schedulers in Scheme.
process:queue. The
value returned is unspecified. The argument to proc should be
ignored. If proc returns, the process is killed.
process:queue and runs the next
process from process:queue. The value returned is
unspecified.
process:queue. If there are no more processes on
process:queue, (slib:exit) is called (See section System).
read-char, read, write-char,
write, display, and newline.
The procedures below were specified in the Revised^2 Report on
Scheme. N.B.: The symbols 1+ and -1+ are not
R4RS syntax. Scheme->C, for instance, barfs on this
module.
0 <= start1 <= end1 <= (string-length string1) 0 <= start2 <= end1 - start1 + start2 <= (string-length string2)
substring-move-left! and substring-move-right! store
characters of string1 beginning with index start1
(inclusive) and ending with index end1 (exclusive) into
string2 beginning with index start2 (inclusive).
substring-move-left! stores characters in time order of
increasing indices. substring-move-right! stores characters in
time order of increasing indeces.
(= 0 (string-length str))
nconc.
(require 'rev4-optional-procedures)
For the specification of these optional procedures, See section `Standard procedures' in Revised(4) Scheme.
For the specification of these optional forms, See section `Numerical operations' in Revised(4) Scheme. The two-arg:* forms are
only defined if the implementation does not support the many-argument
forms.
/.
-.
For the specification of this optional form, See section `Control features' in Revised(4) Scheme.
apply. Only defined for
implementations which don't support the many-argument version.
The procedure rationalize is interesting because most programming languages do not provide anything analogous to it. For simplicity, we present an algorithm which computes the correct result for exact arguments (provided the implementation supports exact rational numbers of unlimited precision), and produces a reasonable answer for inexact arguments when inexact arithmetic is implemented using floating-point. We thank Alan Bawden for contributing this algorithm.
Change occurrences of (delay expression) to
(make-promise (lambda () expression)) and (define
force promise:force) to implement promises if your implementation
doesn't support them
(see section `Control features' in Revised(4) Scheme).
This facility is a generalization of Common LISP unwind-protect,
designed to take into account the fact that continuations produced by
call-with-current-continuation may be reentered.
dynamic-wind calls thunk1, thunk2, and then
thunk3. The value returned by thunk2 is returned as the
result of dynamic-wind. thunk3 is also called just before
control leaves the dynamic context of thunk2 by calling a
continuation created outside that context. Furthermore, thunk1 is
called before reentering the dynamic context of thunk2 by calling
a continuation created inside that context. (Control is inside the
context of thunk2 if thunk2 is on the current return stack).
Warning: There is no provision for dealing with errors or
interrupts. If an error or interrupt occurs while using
dynamic-wind, the dynamic environment will be that in effect at
the time of the error or interrupt.
(require 'eval)
Evaluates expression in the specified environment and returns its
value. Expression must be a valid Scheme expression represented
as data, and environment-specifier must be a value returned by one
of the three procedures described below. Implementations may extend
eval to allow non-expression programs (definitions) as the first
argument and to allow other values as environments, with the restriction
that eval is not allowed to create new bindings in the
environments associated with null-environment or
scheme-report-environment.
(eval '(* 7 3) (scheme-report-environment 5))
=> 21
(let ((f (eval '(lambda (f x) (f x x))
(null-environment))))
(f + 10))
=> 20
Version must be an exact non-negative integer n
corresponding to a version of one of the Revised^n Reports on
Scheme. Scheme-report-environment returns a specifier for an
environment that contains the set of bindings specified in the
corresponding report that the implementation supports.
Null-environment returns a specifier for an environment that
contains only the (syntactic) bindings for all the syntactic keywords
defined in the given version of the report.
Not all versions may be available in all implementations at all times. However, an implementation that conforms to version n of the Revised^n Reports on Scheme must accept version n. An error is signalled if the specified version is not available.
The effect of assigning (through the use of eval) a variable
bound in a scheme-report-environment (for example car) is
unspecified. Thus the environments specified by
scheme-report-environment may be immutable.
This optional procedure returns a specifier for the environment that contains implementation-defined bindings, typically a superset of those listed in the report. The intent is that this procedure will return the environment in which the implementation would evaluate expressions dynamically typed by the user.
Here are some more eval examples:
(require 'eval)
=> #<unspecified>
(define car 'volvo)
=> #<unspecified>
car
=> volvo
(eval 'car (interaction-environment))
=> volvo
(eval 'car (scheme-report-environment 5))
=> #<primitive-procedure car>
(eval '(eval 'car (interaction-environment))
(scheme-report-environment 5))
=> volvo
(eval '(eval '(set! car 'buick) (interaction-environment))
(scheme-report-environment 5))
=> #<unspecified>
car
=> buick
(eval 'car (scheme-report-environment 5))
=> #<primitive-procedure car>
(eval '(eval 'car (interaction-environment))
(scheme-report-environment 5))
=> buick
values takes any number of arguments, and passes (returns) them
to its continuation.
call-with-values calls thunk with a
continuation that, when passed some values, calls proc with those
values as arguments.
Except for continuations created by the call-with-values
procedure, all continuations take exactly one value, as now; the effect
of passing no value or more than one value to continuations that were
not created by the call-with-values procedure is
unspecified.
Here is a read-eval-print-loop which, given an eval, evaluates forms.
reads, repl:evals and writes expressions from
(current-input-port) to (current-output-port) until an
end-of-file is encountered. load, slib:eval,
slib:error, and repl:quit dynamically bound during
repl:top-level.
repl:top-level.
The repl: procedures establish, as much as is possible to do
portably, a top level environment supporting macros.
repl:top-level uses dynamic-wind to catch error conditions
and interrupts. If your implementation supports this you are all set.
Otherwise, if there is some way your implementation can catch error
conditions and interrupts, then have them call slib:error. It
will display its arguments and reenter repl:top-level.
slib:error dynamically bound by repl:top-level.
To have your top level loop always use macros, add any interrupt catching lines and the following lines to your Scheme init file:
(require 'macro) (require 'repl) (repl:top-level macro:eval)
When displaying error messages and warnings, it is paramount that the output generated for circular lists and large data structures be limited. This section supplies a procedure to do this. It could be much improved.
Notice that the neccessity for truncating output eliminates Common-Lisp's See section Format (version 3.0) from consideration; even when variables
*print-level*and*print-level*are set, huge strings and bit-vectors are not limited.
qp writes its arguments, separated by spaces, to
(current-output-port). qp compresses printing by
substituting `...' for substructure it does not have sufficient
room to print. qpn is like qp but outputs a newline
before returning. qpr is like qpn except that it returns
its last argument.
*qp-width* is the largest number of characters that qp
should use.
Requiring debug automatically requires trace and
break.
An application with its own datatypes may want to substitute its own
printer for qp. This example shows how to do this:
(define qpn (lambda args) ...) (provide 'qp) (require 'debug)
defined at top-level in
file `file'.
defined at
top-level in file `file'.
break or
abort, a message will appear when you (require 'break) or
(require 'debug) telling you to type (init-debug). This
is in order to establish a top-level continuation. Typing
(init-debug) at top level sets up a continuation for
break.
breakpoint is called before calling proc1 ....
The following routines are the procedures which actually do the tracing when this module is supplied by SLIB, rather than natively. If defmacros are not natively supported by your implementation, these might be more convenient to use.
(set! symbol (breakf symbol))
or
(set! symbol (breakf symbol 'symbol))
or
(define symbol (breakf function))
or
(define symbol (breakf function 'symbol))
(set! symbol (unbreakf symbol))
The following routines are the procedures which actually do the tracing when this module is supplied by SLIB, rather than natively. If defmacros are not natively supported by your implementation, these might be more convenient to use.
(set! symbol (tracef symbol))
or
(set! symbol (tracef symbol 'symbol))
or
(define symbol (tracef function))
or
(define symbol (tracef function 'symbol))
(set! symbol (untracef symbol))
If (provided? 'getenv):
#f is returned.
If (provided? 'system):
If system is provided by the Scheme implementation, the
net-clients package provides interfaces to common network client
programs like FTP, mail, and Netscape.
tmpnam. If proc returns, then any files named by the
arguments to proc are deleted automatically and the value(s) yielded
by the proc is(are) returned. k may be ommited, in which case
it defaults to 1.
user-email-address returns a string of the form `username@hostname'. If
this e-mail address cannot be obtained, #f is returned.
If user-email-address cannot be supported by the platform, the value of user-email-address is
#f.
getcwd returns a string containing the absolute file name representing
the current working directory. If this string cannot be obtained,
#f is returned.
If getcwd cannot be supported by the platform, the value of getcwd is
#f.
Returns #t if changing directory to file-name makes the current working directory the same as it is before changing directory; otherwise returns #f.
Returns #t if file-name is a fully specified pathname (does not depend on the current working directory); otherwise returns #f.
Returns a URL-string for path on the local host.
Returns a list of the decoded FTP url; or #f if indecipherable. FTP Uniform Resource Locator, ange-ftp, and getit formats are handled. The returned list has four elements which are strings or #f:
Several Scheme packages have been written using SLIB. There are several reasons why a package might not be included in the SLIB distribution:
Once an optional package is installed (and an entry added to
*catalog*, the require mechanism allows it to be called up
and used as easily as any other SLIB package. Some optional packages
(for which *catalog* already has entries) available from SLIB
sites are:
swissnet.ai.mit.edu:pub/scm/slib-psd1-3.tar.gz prep.ai.mit.edu:pub/gnu/jacal/slib-psd1-3.tar.gz ftp.maths.tcd.ie:pub/bosullvn/jacal/slib-psd1-3.tar.gz ftp.cs.indiana.edu:/pub/scheme-repository/utl/slib-psd1-3.tar.gzWith PSD, you can run a Scheme program in an Emacs buffer, set breakpoints, single step evaluation and access and modify the program's variables. It works by instrumenting the original source code, so it should run with any R4RS compliant Scheme. It has been tested with SCM, Elk 1.5, and the sci interpreter in the Scheme->C system, but should work with other Schemes with a minimal amount of porting, if at all. Includes documentation and user's manual. Written by Pertti Kellom\"aki, pk@cs.tut.fi. The Lisp Pointers article describing PSD (Lisp Pointers VI(1):15-23, January-March 1993) is available as http://www.cs.tut.fi/staff/pk/scheme/psd/article/article.html
Go to the first, previous, next, last section, table of contents.