The Scheme Underground char-set and ccp libraries Olin Shivers 98/11/8 Last Update: 98/11/9 This document can be viewed in emacs outline mode, with *'s introducing section headings -- just say M-x outline-mode in emacs. During the SRFI discussion period, the current draft may be found at ftp://ftp.ai.mit.edu/pub/shivers/srfi/cset+ccp.txt * Table of contents ------------------- Abstract Char-sets Char->char partial maps Implementation notes Char-set reference implementation Ccp reference implementation ------------------------------------------------------------------------------- * Abstract ---------- The ability to efficiently represent and manipulate sets of characters and character-to-character partial maps is an unglamorous but very useful capability for text-processing code -- one that tends to pop up in the definitions of other libraries. Hence it is useful to specify a general substrate for this functionality early. This SRFI defines two general libraries that provide this functionality. It is accompanied by reference implementations for the specs. The reference implementations are fairly efficient, straightforwardly portable, and have a "free software" copyright. The implementations are tuned for "small" 7 or 8 bit character types, such as ASCII or Latin-1; the data structures and algorithms would have to be altered for larger 16 or 32 bit character types such as Unicode -- however, the specs have been designed with these larger character type in mind. These libraries are being proposed as a SRFI now, as several forthcoming SRFIs will be defined in terms of them: - string library - delimited input procedures (e.g., READ-LINE) - regular expressions ------------------------------------------------------------------------------- * Char-sets ----------- The ability to efficiently manipulate sets of characters is extremely useful for text-processing code. Encapsulating this functionality in a general, efficiently implemented library can assist all such code. This library defines a new data structure to represent these sets, called a "char-set." The char-set type is distinct from all other types. ** Binding table ---------------- Here is the complete set of bindings -- procedural and otherwise -- exported by this library. In a Scheme system that has a module or package system, these procedures should be contained in a module named "char-set-lib". char-set? char-set= char-set<= char-set-for-each char-set-fold char-set-unfold char-set-unfold! char-set chars->char-set string->char-set ascii-range->char-set predicate->char-set ->char-set char-set-size char-set-members char-set-contains? char-set-every char-set-any char-set-adjoin char-set-delete char-set-adjoin! char-set-delete! char-set-invert char-set-union char-set-intersection char-set-difference char-set-invert! char-set-union! char-set-intersection! char-set-difference! char-set-copy char-set:lower-case char-set:upper-case char-set:alphabetic char-set:numeric char-set:alphanumeric char-set:graphic char-set:printing char-set:whitespace char-set:blank char-set:control char-set:punctuation char-set:hex-digit char-set:ascii char-set:empty char-set:full char-lower-case? char-upper-case? char-alphabetic? char-numeric? char-alphanumeric? char-graphic? char-printing? char-whitespace? char-blank? char-control? char-punctuation? char-hex-digit? char-ascii? ** General procedures --------------------- char-set? x -> boolean Is the object X a character set? char-set= cs1 cs2 ... -> boolean Are the character sets equal? char-set<= cs1 cs2 ... -> boolean Returns true if every character set CSi is a subset of character set CSi+1. char-set-fold kons knil cs -> object This is the fundamental iterator for character sets. Applies the function KONS across the character set CS using initial state value KNIL. That is, if CS is the empty set, the procedure returns KNIL. Otherwise, some element c of CS is chosen; let cs' be the remaining, unchosen characters. The procedure returns (char-set-fold KONS (KONS c KNIL) cs') For example, we could define CHAR-SET-MEMBERS (see below) as (lambda (cs) (char-set-fold cons '() cs)) char-set-for-each proc cs -> unspecific Apply procedure PROC to each character in the character set CS. Note that the order in which PROC is applied to the characters in the set is not specified, and may even change from application to application. char-set-unfold f p g seed -> char-set char-set-unfold! f p g cset0 seed -> char-set This is a fundamental constructor for char-sets. - G is used to generate a series of "seed" values from the initial seed: SEED, (G SEED), (G^2 SEED), (G^3 SEED), ... - P tells us when to stop -- when it returns true when applied to one of these seed values. - F maps each seed value to a character. These characters are collected together to form the character set (for CHAR-SET-UNFOLD), or added to CSET0 in a linear-update (for CHAR-SET-UNFOLD!). More precisely, the following definitions hold (although the actual implementation may be more efficient): (define (char-set-unfold p f g seed) (char-set-unfold! p f g (char-set-copy char-set:empty) seed)) (define (char-set-unfold! p f g cset0 seed) (let lp ((seed seed) (cset cset0)) (if (p seed) cset ; P says we are done. (lp (g seed) ; Loop on (G SEED). (char-set-adjoin! cset (f seed)))))) ; Add (F SEED) to set. ** Creating character sets -------------------------- char-set char1 ... -> char-set Return a character set containing the given characters. chars->char-set chars -> char-set Return a character set containing the characters in the list CHARS. string->char-set s -> char-set Return a character set containing the characters in the string S. predicate->char-set pred -> char-set Returns a character set containing every character c such that (PRED c) returns true. ascii-range->char-set lower upper -> char-set Returns a character set containing every character whose ASCII code lies in the half-open range [LOWER,UPPER). What is the modern-day, Latin-1/Unicode equivalent to this procedure? ->char-set x -> char-set Coerces X into a char-set. X may be a string, character, char-set, or predicate. A string is converted to the set of its constituent characters; a character is converted to a singleton set; a char-set is returned as-is; a predicate is converted to a char-set using PREDICATE->CHAR-SET. This procedure is intended for use by other procedures that want to provide "user-friendly," wide-spectrum interfaces to their clients. ** Querying character sets -------------------------- char-set-members char-set -> character-list This procedure returns a list of the members of CHAR-SET. char-set-contains? char-set char -> boolean This procedure tests CHAR for membership in set char-set. The MIT Scheme character set package called this procedure CHAR-SET-MEMBER?, but the argument order isn't consistent with the name. char-set-size cs -> integer Returns the number of elements in character set CS. char-set-every pred cs -> boolean char-set-any pred cs -> object The CHAR-SET-EVERY procedure returns true if predicate PRED returns true of every character in the character set CS. Likewise, CHAR-SET-ANY applies PRED to every character in character set CS, and returns the first true value it finds. If no character produces a true value, it returns false. The order in which these procedures sequence through the elements of CS is not specified. ** Character-set algebra ------------------------ char-set-invert char-set -> char-set char-set-union char-set1 ... -> char-set char-set-intersection char-set1 char-set2 ... -> char-set char-set-difference char-set1 char-set2 ... -> char-set These procedures implement set complement, union, intersection, and difference for character sets. The union, intersection, and difference operations are n-ary, associating to the left; the difference function requires at least one argument, while union and intersection may be applied to zero arguments. char-set-adjoin cs char1 ... -> char-set char-set-delete cs char1 ... -> char-set Add/delete the CHARi characters to/from character set CS. ** Standard character sets -------------------------- Several character sets are predefined for convenience: char-set:lower-case Lower-case alphabetic chars char-set:upper-case Upper-case alphabetic chars char-set:alphabetic Alphabetic chars char-set:numeric Decimal digits: 0-9 char-set:alphanumeric Alphabetic or numeric char-set:graphic Printing characters except space char-set:printing Printing characters including space char-set:whitespace Whitespace characters char-set:control Control characters char-set:punctuation Punctuation characters char-set:hex-digit A hexadecimal digit: 0-9, A-F, a-f char-set:blank Blank characters char-set:ascii A character in the ASCII set. char-set:empty Empty set char-set:full All characters The first eleven of these correspond to the character classes defined in Posix. Note that there may be characters in CHAR-SET:ALPHABETIC that are neither upper or lower case---this might occur in implementations that use a character type richer than ASCII, such as Unicode. A "graphic character" is one that would put ink on your page. While the exact composition of these sets may vary depending upon the character type provided by the underlying Scheme system, here are the definitions for some of the sets in an ASCII character set: char-set:alphabetic A-Z and a-z char-set:lower-case a-z char-set:upper-case A-Z char-set:graphic Alphanumeric + punctuation char-set:whitespace Space, newline, tab, page, vertical tab, carriage return char-set:blank Space and tab char-set:control ASCII 0-31 and 127 char-set:punctuation !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~ (This spec should also provide the Latin-1 definitions for these sets. I'd appreciate it if some knowledgeable European could send them to me.) char-alphabetic? character -> boolean char-lower-case? character -> boolean char-upper-case? character -> boolean char-numeric? character -> boolean char-alphanumeric? character -> boolean char-graphic? character -> boolean char-printing? character -> boolean char-whitespace? character -> boolean char-blank? character -> boolean char-control? character -> boolean char-punctuation? character -> boolean char-hex-digit? character -> boolean char-ascii? character -> boolean These predicates are defined in terms of the above character sets. ** Linear-update character-set operations ----------------------------------------- These procedures have a hybrid pure-functional/side-effecting semantics: they are allowed, but not required, to side-effect one of their parameters in order to construct their result. An implementation may legally implement these procedures as pure, side-effect-free functions, or it may implement them using side effects, depending upon the details of what is the most efficient or simple to implement in terms of the underlying representation. What this means is that clients of these procedures *may not* rely upon these procedures working by side effect. For example, this is not guaranteed to work: (let ((cs (char-set #\a #\b #\c))) (char-set-adjoin! cs #\d) cs) ; Could be either {a,b,c} or {a,b,c,d}. However, this is well-defined: (let ((cs (char-set #\a #\b #\c))) (char-set-adjoin! cs #\d)) ; {a,b,c,d} So clients of these procedures write in a functional style, but must additionally be sure that, when the procedure is called, there are no other live pointers to the potentially-modified character set (hence the term "linear update"). There are two benefits to this convention: - Implementations are free to provide the most efficient possible implementation, either functional or side-effecting. - Programmers may nonetheless continue to assume that character sets are purely functional data structures: they may be reliably shared without needing to be copied, uniquified, and so forth. Note that pure functional representations are the right thing for ASCII- or Latin-1-based Scheme implementations, since a char-set can be represented in an ASCII Scheme with 4 32-bit words. Pure set-algebra operations on such a representation are very fast and efficient. Programmers who code using linear-update operations are guaranteed the system will provide the best implementation across multiple platforms. In practice, these procedures are most useful for efficiently constructing character sets in a side-effecting manner, in some limited local context, before passing the character set outside the local construction scope to be used in a functional manner. Scheme provides no assistance in checking the linearity of the potentially side-effected parameters passed to these functions --- there's no linear type checker or run-time mechanism for detecting violations. (But sophisticated programming environments, such as DrScheme, might help.) char-set-copy cs -> char-set Returns a copy of the character set CS. "Copy" means that if either the input parameter or the result value of this procedure is passed to one of the linear-update procedures described below, the other character set is guaranteed not to be altered. (A system that provides pure-functional implementations of the rest of the linear-operator suite could implement this procedure as the identity function.) char-set-adjoin! cs char1 ... -> char-set Add the CHARi characters to character set CS, and return the result. This procedure is allowed, but not required, to side-effect CS. char-set-delete! cs char1 ... -> char-set Remove the CHARi characters to character set CS, and return the result. This procedure is allowed, but not required, to side-effect CS. char-set-invert! char-set char-set char-set-union! char-set1 char-set2 ... -> char-set char-set-intersection! char-set1 char-set2 ... -> char-set char-set-difference! char-set1 char-set2 ... -> char-set These procedures implement set complement, union, intersection, and difference for character sets. They are allowed, but not required, to side-effect their first parameter. The union, intersection, and difference operations are n-ary, associating to the left. ------------------------------------------------------------------------------- * Char->char partial maps ------------------------- A CCP maps a char to another char or #f. The domain of a CCP is the set of characters that are mapped to some character. A *total* CCP is a CCP whose domain is char-set:full -- that is, it's a simple char->char map. All functions ending with ! are efficient linear-update functions. They are allowed, but not required, to construct their result by side-effecting their first ccp parameter. You may only use these functions in a context where you know there are no other live references to the potentially-modified ccp parameter, since these references are not well-defined after one of these calls. You typically use these functions to construct a ccp in a local context (e.g., in a tight loop). In the definitions below, when reference is made to a "freshly allocated" ccp, it means one that is distinct from any other for the purposes of the linear-update functions. It may be used in a linear-update operation without affecting the value of any other ccp. When reference is made to "shared" ccps, it means a pair of ccps that are *not* distinct from one another for the purposes of the linear-update functions -- if one of the shared ccp's is used in a linear-update operation, the other's value is not well-defined after the operation. Note that it would be perfectly legal for an implementation to define the linear-update functions to be completely functional, and CCP-COPY to be the identity function (lambda (x) x). The ccp type is distinct from all other types. ** Binding table ---------------- Here is the complete set of bindings -- procedural and otherwise -- exported by this library. In a Scheme system that has a module or package system, these procedures should be contained in a module named "ccp-lib". ccp:0 ccp:1 ccp:upcase ccp:downcase ccp? ccp= ccp<= ccp-domain ccp->alist ccp-copy ccp-restrict ccp-delete ccp-adjoin ccp-extend ccp-restrict! ccp-delete! ccp-adjoin! ccp-extend! alist->ccp proc->ccp constant-ccp extend-ccp/mappings construct-ccp alist->ccp! proc->ccp! constant-ccp! extend-ccp/mappings! construct-ccp! ccp-compose ccp/mappings ccp-unfold ccp-unfold! ccp-tr ccp-map ccp-map! ccp-app ccp-fold ccp-for-each ** Predefined CCPs ------------------ ccp:0 The empty partial map -- domain is empty set. ccp:upcase The upcase total map. Domain is char-set:full. ccp:downcase The downcase total map. Domain is char-set:full. ccp:1 The identity total map. Domain is char-set:full. ** Basic CCP operations ----------------------- (ccp? x) -> boolean Is X a CCP? (ccp-domain ccp) -> char-set The domain of the CCP. (ccp= ccp1 ...) -> boolean Return true iff the ccps are all the same -- i.e., they all have identical domains, and all map each character in the domain to the same value. (ccp<= ccp1 ...) -> boolean Return true iff each ccp in the parameter list is <= the following one. ccp1 <= ccp2 iff the domain of ccp1 is a subset of the domain of ccp2, and the ccps are equal over ccp1's domain. Hence ccp:0 is the least ccp. (ccp-copy ccp) -> ccp Copies the ccp -- there are guaranteed no other references to the returned value, so it may be safely used in a linear-update function. ** CCP constructors ------------------- (ccp-delete ccp char1 ...) -> ccp (ccp-delete! ccp char1 ...) -> ccp Remove the characters from CCP's domain. If no characters are specified, CCP-DELETE is permitted to return CCP (as opposed to a distinct copy). (ccp-adjoin ccp from-char1 to-char1 ...) -> ccp (ccp-adjoin! ccp from-char1 to-char1 ...) -> ccp Add the mappings {FROM-CHARi -> TO-CHARi} to CCP. If no mappings are specified, CCP-ADJOIN is permitted to return CCP (as opposed to a distinct copy). (ccp-restrict ccp char-set) -> ccp (ccp-restrict! ccp char-set) -> ccp Restrict CCP to domain CHAR-SET. CCP-RESTRICT always returns a freshly allocated CCP. (ccp-extend ccp1 ...) -> ccp (ccp-extend! ccp1 ccp2 ...) -> ccp (ccp-extend CCP1 CCP2) extends or overrides CCP1 with CCP2 -- CCP2's mappings take precedence over CCP1's, etc. The domain of the resulting ccp is the union of the domains of the parameters. Niladic case: (ccp-extend) = ccp:0. If only one parameter is passed to CCP-EXTEND, it is permitted to return exactly that value (as opposed to a distinct copy). (ccp-compose ccp1 ...) -> ccp Compose the ccps. Niladic case: (ccp-compose) = ccp:1. The domain of (ccp-compose ccp1 ccp2) is { c | (and (in c (domain ccp2)) (in (ccp2 c) (domain ccp1))) } Note that this is simple function composition when the CCP's are total maps. If only one parameter is passed to CCP-EXTEND, it is permitted to return exactly that value (as opposed to a distinct copy). (constant-ccp char [domain base-ccp]) -> ccp (constant-ccp! char domain base-ccp) -> ccp Extend BASE-CCP with the map taking every char in DOMAIN to CHAR. DOMAIN defaults to char-set:full. BASE-CCP defaults to CCP:0. CONSTANT-CCP always returns a freshly-allocated ccp. (alist->ccp cc-alist [base-ccp]) -> ccp (alist->ccp! cc-alist base-ccp) -> ccp BASE-CCP is extended by the char->char alist; it defaults to ccp:0. ALIST->CCP always returns a freshly allocated ccp. (ccp/mappings from1 to1 ... fromN toN) -> ccp (extend-ccp/mappings base-ccp from1 to1 ... fromN toN) -> ccp (extend-ccp/mappings! base-ccp from1 to1 ... fromN toN) -> ccp Extends BASE-CCP, which defaults to ccp:0, with the FROM/TO mappings. Each FROM may be a string or a (lo-char . hi-char) range pair. Each TO may be a string or a lo-char range start. If a TO string is shorter than the corresponding FROM string or range, it it is replicated to match the length of the FROM. For example, we can map all the lowercase letters to the space character with the FROM = (#\a . #\z), and TO = " " (extend-ccp/mappings ccp:1 ; Identity otherwise. "AEIOU" "EIOUA" ; Rotate upper-case vowels. "0123456789" "01" ; Odds -> 1, evens -> 0. '(#\a . #\z) #\A) ; Capitalize letters. If EXTEND-CCP/MAPPINGS is not given any from/to pairs, it is permitted to return exactly BASE-CCP (as opposed to a distinct copy). This is not the greatest name. (proc->ccp proc [dchar-set base-ccp]) -> ccp (proc->ccp! proc dchar-set base-ccp) -> ccp Extend BASE-CCP with the the ccp that maps each char c in domain set DCHAR-SET to (PROC c). DCHAR-SET defaults to char-set:full; BASE-CCP defaults to ccp:0. PROC->CCP always returns a freshly-allocated ccp. (construct-ccp ccp elt1 ...) -> ccp (construct-ccp! ccp elt1 ...) -> ccp This is the "kitchen sink" general-purpose CCP constructor. It extends CCP using the specifications passed as the ELTi arguments. The ELTi can be the following (lo-char . hi-char) to-string As in CCP/MAPPINGS (lo-char . hi-char) lo-char As in CCP/MAPPINGS from-string to-string As in CCP/MAPPINGS from-string lo-char As in CCP/MAPPINGS ccp As in CCP-EXTEND alist As in ALIST->CCP domain char As in CONSTANT-CCP domain proc As in PROC->CCP The ccp is constructed in a left-to-right traversal of the elts; later elts override earlier ones. Example: (construct-ccp ccp:0 "aeiou" "AEIOU" ; Upcase vowels '((#\y . #\0) (#\n . #\1)) ; y->0 n->1 char-set:hex-digit char-downcase ; downcase hex char-set:whitespace #\-) ; whitespace -> - If CONSTRUCT-CCP is not given any ELTi values, it is permitted to return exactly CCP (as opposed to a distinct copy). (ccp-unfold p f g seed) -> ccp (ccp-unfold! p f g ccp0 seed) -> ccp These are fundamental constructors for CCPs. - G is used to generate a series of "seed" values from the initial seed: SEED, (G SEED), (G^2 SEED), (G^3 SEED), ... - P tells us when to stop -- when it returns true when applied to one of these seed values. - F maps each seed value to two character values, giving a FROM -> TO mapping. CCP-UNFOLD collects the mappings together to form the result ccp; CCP-UNFOLD adds the mappings to CCP0 in a linear update to form the result. Later mappings override earlier mappings. More precisely, the following definition holds: (define (ccp-unfold p f g seed) (ccp-unfold! p f g (ccp-copy ccp:0) seed)) (define (ccp-unfold! p f g ccp0 seed) (let lp ((seed seed) (ccp ccp0)) (if (p seed) ccp ; P says we are done. (call-with-values (lambda () (f seed)) ; (F SEED) (lambda (from to) ; -> FROM/TO (lp (g seed) ; Loop on (G SEED). (ccp-adjoin! ccp from to))))))) ; Add FROM/TO mapping. ** Using CCPs ------------- (ccp-app ccp char) -> char or #f Apply the ccp to the character. Return false if the character is not in the ccp's domain. (ccp-tr ccp s [start end]) -> string Map CCP over string S. Chars in S not in CCP's domain are dropped, which gives the functionality of "tr -d". (ccp-map ccp s [start end]) -> string (ccp-map! ccp s [start end]) -> unspecified Identical to CCP-TR, but causes an error if a char in S is not in CCP's domain. (ccp-fold kons knil ccp) -> value Fold KONS across the map CCP: - If CCP is the empty ccp, return KNIL. - Otherwise, choose some mapping c -> c' from the map. Let CCP' be the CCP with character C removed from its domain. Return (ccp-fold kons (kons c c' knil) ccp'). Example: (define (ccp->alist ccp) (ccp-fold (lambda (from to lis) (cons (cons from to) lis)) '() ccp)) (ccp-for-each proc ccp) -> unspecified Apply PROC to each mapping in CCP: (PROC from to). Example: (ccp-for-each (lambda (from to) (format "~s -> ~s\n" from to)) ccp) (ccp->alist ccp) -> char/char-alist Return the CCP realised as an alist. Example: (ccp->alist (range-ccp "aeiou" "AEIOU")) => '((#\a . #\A) (#\e . #\E) (#\i . #\I) (#\o . #\O) (#\u . #\U)) ** Examples ----------- ;;; Delete whitespace characters: (lambda (s) (ccp-tr (ccp-restrict ccp:1 char-set:not-whitespace) s)) ;;; Lowercase all hex digits; delete everything else. (lambda (s) (ccp-tr (ccp-restrict ccp:downcase char-set:hex) s)) ;;; Lowercase: (lambda (s) (ccp-map (extend-ccp/mappings ccp:1 '(#\A . #\Z) #\a) s)) ------------------------------------------------------------------------------- * Implementation notes ----------------------- The char-set reference code uses a rather simple-minded, inefficient representation for ASCII/Latin-1 char-sets -- a 256-character string. The character whose code is I is in the set if S[I] = ASCII 1; not in the set if S[I] = ASCII nul. A much faster and denser representation would be 16 or 32 bytes worth of bit string. A portable implementation using bit sets awaits a bitwise logical-op standard. "Large" character types, such as Unicode, should use a sparse representation, taking care that the Latin-1 subset continues to be represented with a dense 32-byte bit set. CCP's are easy to represent for 7- and 8-bit character types such as Latin-1 or ASCII: (define-record ccp domain ; The domain char-set map) ; 128 (ASCII) or 256 (Latin-1) character string For 16- or 32-bit character types, we have to be somewhat fancier. Perhaps (define-record ccp domain ; The domain char-set map ; Sorted vector of (char . string) pairs specifying ; the map. id?) ; If true, mappings not specified by MAP are identity ; mapping. If false, MAP must specify a mapping for ; every char in DOMAIN. A (char . string) element in MAP specifies a mapping for the contiguous sequence of L chars beginning with CHAR (in the sequence of the underlying char type representation), where L is the length of STRING. These MAP elements are sorted by CHAR, so that binary search can be used to get from an input character C to the right MAP element quickly. This representation should be reasonably compact for standard mappings on, say, a Unicode CCP. An implementation would probably want to have special fields for the Latin-1 subset of the ccp's Unicode domain, and use sparse representations for the rest of the domain -- although Israelis, Russians, Arabs, Chinese, et al. might fail to see this as much of a win. This trick might also be handy when implementing the char-set library for Unicode characters. The reference implementation includes marker fields in the record to indicate whether the domain and map structures are shared or linear. This allows one to cheaply build linear ccps that actually share structure "under the hood" with a "copy on write" policy. See the code for details. ------------------------------------------------------------------------------- * Changes ----------------------------------- 11/15/98 Added text giving names for the packages. Added some type-checking code to the reference implementation. ------------------------------------------------------------------------------- * Char-set reference implementation ----------------------------------- The current source can be found at ftp://ftp.ai.mit.edu/pub/shivers/srfi/cset-lib.scm It will appear here in the final SRFI. ------------------------------------------------------------------------------- * CCP reference implementation ------------------------------ The current source can be found at ftp://ftp.ai.mit.edu/pub/shivers/srfi/ccp-lib.scm It will appear here in the final SRFI.