Re: 7.1 string operations (was Re: Ann: SWI-Prolog 6.5.3)

On 25/11/2013, at 9:44 AM, Jan Wielemaker wrote:

> On 11/22/2013 01:38 AM, Richard A. O'Keefe wrote:
>> OK.  If you think strings are a good data type, shouldn't they have
>> more operations?  And should the manual still be saying
>> 	new code should consider using atoms
> 
> According to grep, that is no longer in the manual now.

OK, that was quoted from the on-line help in a fairly recent version.

>> Would it be a good idea to
>> document that/whether strings work in UTF-8, and whether "characters"
>> in the documentation of string_length/2 and sub_string/5 means "bytes"
>> or "Unicode code-points"?  Would it be a good idea to offer the
> 
> Strings are sequences of characters.  SWI-Prolog is Unicode aware,
> so they are sequences of Unicode characters.   I think there is little
> point repeating that over and over.

This is in the context of a fairly recent version of SWI Prolog
whose online help(4-24) says explicitly
	"Strings are stored as A BYTE ARRAY".
and refers to "bytes" several other times.

I agree that a Unicode-aware system doesn't need to mention Unicode
over and over, but that's *except* where bytes are explicitly mentioned.
I understand from earlier remarks in your message that this help text
is now different.

> 
>>    span_left(String, Set, Before[, Length[, After]])
>>    span_right(String, Set[[, Before], Length], After)
>> predicates that Xerox Quintus Prolog did?  -- quite helpful for
>> tokenising.
> 
> Found the docs.  I'm not really convinced.  Set is an atom,
> code list or not(Set) as I understand it.

You have mistaken the pips for the fruit.
The fruit here is having *some* way to match a sequence
of characters of some kind.  The particular representation
of a set is just pips.  (As you may know, apple pips contain
cyanide (:-).)

>  These simple
> sets do not play very well with Unicode.  Even removing
> white space is already getting hard this way.  You'd want
> at least something that allows for character ranges and
> Unicode classes similar to regex.

Actually, the same _interface_ was used in Xerox Quintus Prolog,
where characters were 16 bits.  The backing code in InterLisp-D
was not much like the C code for the Unix ports, of course.
The Xerox XNS character set didn't come with a gazillion versions
of white space and fifty copies of the digits...

A decent representation of character sets for Unicode is needed.
And there need to be two separate things:
 - an efficient representation as a data structure
 - a readable representation for people to enter.
For that matter, the readable representation could very well be
a POSIX or PCRE character class sans enclosing brackets.

My Smalltalk system uses a data structure inspired by UNIX
i-nodes.
 - a vector of 256 bits (Latin 1)
 - an array of 255 vectors of 256 bits (the rest of the BMP)
 - an array of 16 arrays of 256 vectors of 256 bits (the astral planes).
There are read-only empty vectors and arrays shared so that space is only
allocated where a 1 bit forces it.  There are CharacterSet and
CharacterSetComplement so that not(Set) is cheap.  And this _still_
doesn't handle sets defined by character classes well; that needs
another data structure I haven't built yet.  There is probably a much
better data structure or 3 that I have completely failed to imagine.
I would be interested to hear suggestions.

It's *because* implementing sets of Unicode characters well is so
complex that it doesn't belong in user code.

> We probably want a split-like predicate, similar to atomic_list_concat/3.
> The naming is a bit hard as there is no atom in this name.
> Maybe atomic_list_string(?List, +Separator, ?String)?

Such a thing may well be useful, but it would be hideously
inappropriate for the tasks that span_{left,right} were invented for,
where you *just* want the first (or last) chunk, and the next time
you will be using a *different* set.

> Then there is long pending thing called regular expressions.  Strings
> is the right moment to introduce them.  But, how?  Notable, which code
> base and according to which of the many regex standards?

I'd recommend re2.
http://code.google.com/p/re2/
Fast, low memory, multithread-friendly, and about as Perl-compatible
as you can get while still being guaranteed linear time.
Actively maintained, too; the latest version is 2013-10-24.

This would do more than the span_left family, although it wouldn't
substitute for the less commonly useful span_right.