Anything that doesn't fall neatly into any of the other categories winds up here.
The batch procedures provide a way to write and execute portable scripts
for a variety of operating systems. Each batch:
procedure takes
as its first argument a parameter-list (see section Parameter lists). This
parameter-list argument parms contains named associations. Batch
currently uses 2 of these:
batch-port
batch-dialect
`batch.scm' uses 2 enhanced relational tables (see section Database Utilities) to store information linking the names of
operating-system
s to batch-dialect
es.
operating-system
and batch-dialect
tables and adds
the domain operating-system
to the enhanced relational database
database.
batch:platform
is set to (software-type)
(see section Configuration) unless (software-type)
is unix
,
in which case finer distinctions are made.
batch:call-with-output-script
writes an appropriate
header to file and then calls proc with file as the
only argument. If file is a string,
batch:call-with-output-script
opens a output-file of name
file, writes an appropriate header to file, and then calls
proc with the newly opened port as the only argument. Otherwise,
batch:call-with-output-script
acts as if it was called with the
result of (current-output-port)
as its third argument.
#t
if successful, #f
if not.
batch:apply-chop-to-fit
calls proc with arg1,
arg2, ..., and chunk, where chunk is a subset of
list. batch:apply-chop-to-fit
tries proc with
successively smaller subsets of list until either proc
returns non-false, or the chunks become empty.
The rest of the batch:
procedures write (or execute if
batch-dialect
is system
) commands to the batch port which
has been added to parms or (copy-tree parms)
by the
code:
(adjoin-parameters! parms (list 'batch-port port))
batch:try-system
(below) with arguments, but signals an
error if batch:try-system
returns #f
.
These functions return a non-false value if the command was successfully
translated into the batch dialect and #f
if not. In the case of
the system
dialect, the value is non-false if the operation
suceeded.
batch-port
in parms which executes
the program named string1 with arguments string2 ....
batch-port
in parms which executes
the batch script named string1 with arguments string2
....
Note: batch:run-script
and batch:try-system
are not the
same for some operating systems (VMS).
batch-port
in
parms.
batch-port
in parms which create a
file named file with contents line1 ....
batch-port
in parms which deletes
the file named file.
batch-port
in parms which renames
the file old-name to new-name.
In addition, batch provides some small utilities very useful for writing scripts:
(truncate-up-to "/usr/local/lib/slib/batch.scm" "/") => "batch.scm"
str
but with the suffix string old
removed and the suffix string new appended. If the end of
str does not match old, an error is signaled.
(replace-suffix "/usr/local/lib/slib/batch.scm" ".scm" ".c") => "/usr/local/lib/slib/batch.c"
equal?
to elements of
list2, then those elements will appear first and in the order of
list1.
equal?
to elements of
list1, then those elements will appear last and in the order of
list2.
batch-dialect
to be used for the
operating-system named osname. os->batch-dialect
uses the
tables added to database by batch:initialize!
.
Here is an example of the use of most of batch's procedures:
(require 'database-utilities) (require 'parameters) (require 'batch) (define batch (create-database #f 'alist-table)) (batch:initialize! batch) (define my-parameters (list (list 'batch-dialect (os->batch-dialect batch:platform)) (list 'platform batch:platform) (list 'batch-port (current-output-port)))) ;gets filled in later (batch:call-with-output-script my-parameters "my-batch" (lambda (batch-port) (adjoin-parameters! my-parameters (list 'batch-port batch-port)) (and (batch:comment my-parameters "================ Write file with C program.") (batch:rename-file my-parameters "hello.c" "hello.c~") (batch:lines->file my-parameters "hello.c" "#include <stdio.h>" "int main(int argc, char **argv)" "{" " printf(\"hello world\\n\");" " return 0;" "}" ) (batch:system my-parameters "cc" "-c" "hello.c") (batch:system my-parameters "cc" "-o" "hello" (replace-suffix "hello.c" ".c" ".o")) (batch:system my-parameters "hello") (batch:delete-file my-parameters "hello") (batch:delete-file my-parameters "hello.c") (batch:delete-file my-parameters "hello.o") (batch:delete-file my-parameters "my-batch") )))
Produces the file `my-batch':
#!/bin/sh # "my-batch" build script created Sat Jun 10 21:20:37 1995 # ================ Write file with C program. mv -f hello.c hello.c~ rm -f hello.c echo '#include <stdio.h>'>>hello.c echo 'int main(int argc, char **argv)'>>hello.c echo '{'>>hello.c echo ' printf("hello world\n");'>>hello.c echo ' return 0;'>>hello.c echo '}'>>hello.c cc -c hello.c cc -o hello hello.o hello rm -f hello rm -f hello.c rm -f hello.o rm -f my-batch
When run, `my-batch' prints:
bash$ my-batch mv: hello.c: No such file or directory hello world
(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
eq?
is used to test for membership by all the procedures below
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
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
butlast
returns all but the last n elements of
lst.
Example:
(butlast '(1 2 3 4) 3) => (1) (butlast '(1 2 3 4) 4) => ()
nthcdr
takes n cdr
s 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)
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
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
cdr
s 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).
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.
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 | # ]
Documentation syntax: Uppercase characters represent the corresponding control directive characters. Lowercase characters represent control directive parameter descriptions.
~A
display
does).
~@A
~mincol,colinc,minpad,padcharA
~S
write
does).
~@S
~mincol,colinc,minpad,padcharS
~D
~@D
~:D
~mincol,padchar,commacharD
~X
~@X
~:X
~mincol,padchar,commacharX
~O
~@O
~:O
~mincol,padchar,commacharO
~B
~@B
~:B
~mincol,padchar,commacharB
~nR
~n,mincol,padchar,commacharR
~@R
~:R
~:@R
~P
~@P
y
and ies
.
~:P
~P but jumps 1 argument backward.
~:@P
~@P but jumps 1 argument backward.
~C
~@C
#\
prefixing).
~:C
^C
for ASCII 03).
~F
~width,digits,scale,overflowchar,padcharF
~@F
~E
E
ee).
~width,digits,exponentdigits,scale,overflowchar,padchar,exponentcharE
~@E
~G
~width,digits,exponentdigits,scale,overflowchar,padchar,exponentcharG
~@G
~$
~digits,scale,width,padchar$
~@$
~:@$
~:$
~%
~n%
~&
~n&
~&
and then n-1 newlines.
~|
~n|
~~
~n~
~
<newline>
~:
<newline>
~@
<newline>
~T
~@T
~colnum,colincT
~?
~@?
~(str~)
string-downcase
).
~:(str~)
string-capitalize
.
~@(str~)
string-capitalize-first
.
~:@(str~)
string-upcase
.
~*
~n*
~:*
~n:*
~@*
~n@*
~[str0~;str1~;...~;strn~]
~n[
~@[
~:[
~;
~:;
~{str~}
~n{
~:{
~@{
~:@{
~^
~n^
~n,m^
~n,m,k^
~:A
#f
as an empty list (see below).
~:S
#f
as an empty list (see below).
~<~>
~:^
~mincol,padchar,commachar,commawidthD
~mincol,padchar,commachar,commawidthX
~mincol,padchar,commachar,commawidthO
~mincol,padchar,commachar,commawidthB
~n,mincol,padchar,commachar,commawidthR
~I
~F~@Fi
with passed parameters for
~F
.
~Y
~K
~?.
~!
~_
#\space
character
~n_
#\space
characters.
~/
#\tab
character
~n/
#\tab
characters.
~nC
integer->char
. n must be a positive decimal number.~:S
#<...>
as strings "#<...>"
so that the format output can always
be processed by read
.
~:A
#<...>
as strings "#<...>"
so that the format output can always
be processed by read
.
~Q
~:Q
~F, ~E, ~G, ~$
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.
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
)
#f
)
~E
printing. (default
#\E
)
~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.
~
, 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).
~A
and ~S
which print in
uppercase. (Elk implements ~a
, ~s
, ~~
, and
~%
(no directive parameters or modifiers)).
~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
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.
#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)
current-input-port
.
#f
is returned. port may be omitted, in which case it defaults to
the value returned by current-input-port
.
current-input-port
.
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).
pretty-print
s 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))
(current-output-port)
.
outfile is a port or a string. If no outfile is specified
then current-output-port
is assumed. These expanded expressions
are then pretty-print
ed 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")
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)
require
s printf
and scanf
and additionally defines
the symbols:
(current-input-port)
.
(current-output-port)
.
(current-error-port)
.
Each function converts, formats, and outputs its arg1 ... arguments according to the control string format argument and returns the number of characters output.
printf
sends its output to the port (current-output-port)
.
fprintf
sends its output to the port port. sprintf
string-set!
s locations of the non-constant string argument
str to the output characters.
Note: sprintf should be changed to a macro so a
substring
expression could be used for the str argument.
The string format contains plain characters which are copied to the output stream, and conversion specifications, each of which results in fetching zero or more of the arguments arg1 .... The results are undefined if there are an insufficient number of arguments for the format. If format is exhausted while some of the arg1 ... arguments remain unused, the excess arg1 ... arguments are ignored.
The conversion specifications in a format string have the form:
% [ flags ] [ width ] [ . precision ] [ type ] conversion
An output conversion specifications consist of an initial `%' character followed in sequence by:
scanf
functions with the `%i' conversion (see section Standard Formatted Input).
6
. If the precision is explicitly 0
,
the decimal point character is suppressed.
For the `%g' and `%G' conversions, the precision specifies how
many significant digits to print. Significant digits are the first
digit before the decimal point, and all the digits after it. If the
precision is 0
or not specified for `%g' or `%G', it is
treated like a value of 1
. If the value being printed cannot be
expressed accurately in the specified number of digits, the value is
rounded to the nearest number that fits.
For exact conversions, if a precision is supplied it specifies the
minimum number of digits to appear; leading zeros are produced if
necessary. If a precision is not supplied, the number is printed with
as many digits as necessary. Converting an exact `0' with an
explicit precision of zero produces no characters.
scanf
for input (see section Standard Formatted Input).
Note: Inexact conversions are not supported yet.
write
(which can be read using read
); otherwise,
output is as display
prints. A precision specifies the maximum
number of characters to output; otherwise as many characters as needed
are output.
Note: `%a' and `%A' are SLIB extensions.
Each function reads characters, interpreting them according to the control string format argument.
scanf-read-list
returns a list of the items specified as far as
the input matches format. scanf
, fscanf
, and
sscanf
return the number of items successfully matched and
stored. scanf
, fscanf
, and sscanf
also set the
location corresponding to arg1 ... using the methods:
set!
set-car!
set-cdr!
vector-set!
substring-move-left!
The argument to a substring
expression in arg1 ... must
be a non-constant string. Characters will be stored starting at the
position specified by the second argument to substring
. The
number of characters stored will be limited by either the position
specified by the third argument to substring
or the length of the
matched string, whichever is less.
The control string, format, contains conversion specifications and other characters used to direct interpretation of input sequences. The control string contains:
Unless the specification contains the `n' conversion character (described below), 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 characters; it extends to the next inappropriate character or until the field width, if specified, is exhausted.
Note: This specification of format strings differs from the ANSI C and POSIX specifications. In SLIB, white space before an input field is not skipped unless white space appears before the conversion specification in the format string. In order to write format strings which work identically with ANSI C and SLIB, prepend whitespace to all conversion specifications except `[' and `c'.
The conversion code indicates the interpretation of the input field; For a suppressed field, no value is returned. The following conversion codes are legal:
scanf
. No input is consumed by %n
.
scanf
cannot read a null string.
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.
#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
#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.
Note: The Tektronix graphics support files need more work, and are not complete.
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.
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.
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
Go to the first, previous, next, last section, table of contents.