[gambit-list] SRFI 14 and data structures in gambit/lib/gambit/char/char#.scm

Marc Feeley feeley at iro.umontreal.ca
Thu May 18 09:04:21 EDT 2023


The Gambit RTS implements the Unicode tables with a few homogeneous vectors that encode the properties of the characters.  The design is optimized for speed, i.e. the execution time of predicates like (char-lower-case? char), and character conversions like (char-downcase char), and string conversions like (string-downcase string).

Most of the information is contained in the ##unicode-class u8vector which has 1 byte for the relevant Unicode characters (the first 205744 characters).  This u8vector is indexed directly with the character code (not a binary search).  The byte encodes the “character class” like this:

;; code = 0-9     => digit, with a code that is the digit value
;; code = 10      => no interesting class
;; code = 11      => whitespace
;; code = 12      => other class
;; code = 13-94   => upper case class
;; code = 95-97   => title case class
;; code = 98-199  => lower case class

These ranges are computed automatically by reading the Unicode properties files (see the macro-define-unicode-tables macro in lib/gambit/char/char#.scm which does this processing at macro expansion time).

Using a directly indexed u8vector makes it fast to check the basic properties, such as (char-lower-case? char), (char-numeric? char), and (char-whitespace? char).

Other vectors encode the information required to upcase and downcase characters using a “distance” information.  For example (char-downcase char) is essentially implemented like this:

 (define (char-downcase char)
   (let* ((c (char->integer char))
          (d (+ c (quotient (s32vector-ref ##unicode-downcase-dist (u8vector-ref ##unicode-class c)) 2))))
     (integer->char d)))

 (char-downcase #\X)  =>  #\x
 (char-downcase #\a)  =>  #\a

The lower bit of the “distance” information is usually 0.  It is 1 when there is not a mapping from one character to one character, for example (string-upcase "ß") => "SS"

So for implementing SRFI 14 efficiently, I think the above encoding should be used when possible for the predefined character sets, i.e. char-set:lower-case, char-set:upper-case, char-set:letter, char-set:digit, etc. It will allow quickly testing membership. The encoding mentionned by John (which requires a binary search) is a good implementation for general character sets which typically have groups of contiguous characters in or out of the set.  It would be wasteful in time and space to implement the predefined character sets with the general representation (for example each of char-set:lower-case, char-set:upper-case, char-set:letter occupy about 5 KB and require a binary search to test membership).

Marc



> On May 17, 2023, at 1:32 PM, Bradley Lucier <lucier at math.purdue.edu> wrote:
> 
> Marc:
> 
> I'd like to have an implementation of SRFI 14 (character sets) that works with the entire unicode character set rather than just the 256-character Latin1 subset
> 
> I think one needs a data structure that allows compact encoding of relatively large (about $2^{21}$ elements) sets of positive integers that have lots of contiguous subsets.
> 
> At any rate, I thought you may have solved this problem in gambit/lib/gambit/char/char#.scm, but for the life of me I can't figure out what you're doing there.
> 
> Can your data sets for encoding Unicode properties be used for an efficient SRFI 14 implementation?
> 
> Brad
> 




More information about the Gambit-list mailing list