Re: SWI-Prolog 7.1.3

On 12/17/2013 05:25 AM, Richard A. O'Keefe wrote:
>
> On 16/12/2013, at 9:33 PM, Jan Wielemaker wrote:
>>> I have not been able to figure out any way to use the
>>> read_string predicates to do any of the string reading
>>> I have uses for; use cases for those predicates would
>>> be of interest to me.
>>
>> The observation was that split_string/4 is very
>> useful.  read_string/5 provides the same functionality
>> incrementally.
>
> I am astonished by the assertion "that split_string/4
> is very useful".  Let me quote the manual.
>
>      split_string(+String, +SepChars, +PadChars, -SubStrings)
>
>      Break String into SubStrings.
>      The SepChars argument provides the characters that
>      act as separators and thus the length of SubStrings
>      is one more than the number of separators found.
>      Leading and trailing characters for each substring
>      that appear in PadChars are removed from the substring.
>      The input arguments can be either atoms, strings or
>      char/code lists.  Compatible with ECLiPSe.
>
> The first thing I note is that there are two arguments that
> specify a set of characters, but there is no set-of-characters
> data type.  (See pllib.htm section 1.5.)

That was noted.  ECliPSe is 8-bit only, so it doesn't matter too
much.  Joachim and I decided that we would look into a more abstract
character set notion later.  Trying to solve that right away would
have complicated getting to an agreement on the primitives too much.

> Consider an example.  I have a string containing text.
> I want to split it at white space, and then remove leading
> and trailing punctuation characters from each "word".
>
>   - Problem: there are 434 "Po" characters in Unicode 6.3,
>     plus 74 "Ps" characters, 73 "Pe" characters,
>     I _really_ don't want to type them by hand.  With
>     pllib.htm 1.5 it would be possible to do
>
>     compile_uniset(zs+zl+zp+pd+pi+"\t\n\f", Layout),
>     compile_uniset(po+ps+pe, Punctuation),
>     split_string(String, Layout, Punctuation, Substrings)
>
>     This is not an unrealistic example.

Indeed.  We'll check out pllib.htm before deciding on a
character set notion.

>   - Problem: if I'm reading the documentation correctly,
>     this doesn't do at all what I want.  I want a string
>     splitter that takes *RUNS* of separator characters
>     as separators.  Suppose the input is
>	"Lorem ipsum.  Dolor sit amet. "
>     If the separators include spaces, and the number of
>     Substrings is one more than the number of spaces,
>     then this would return
>	["Lorem","ipsum","","Dolor","sit","amet",""]
>                           ^^                      ^^
>     with empty strings that are worse than useless to me.

You deal with runs of separator characters by making
SepChars and PadChars the same.  Then you never and up
with empty strings.  I guess the most typical case for
this is if these sets represent white space.

>     I do have a few use cases where empty fields are possible,
>     but they are greatly outnumbered by use cases needing
>     runs of separators.
>
>     Note in particular that if you use this with Unix filenames
>     it will go wrong.  The parts of "/foo//bar///ugh" are
>     "foo", "bar", and "ugh" -- there are no empty parts there.

So,

    ?- split_string("/foo//bar///ugh", "/", "/", L).
    L = ["foo", "bar", "ugh"].

And

    ?- split_string("libuuid:x:100:101::/var/lib/libuuid:/bin/sh", ":", 
"", L).
    L = ["libuuid", "x", "100", "101", "", "/var/lib/libuuid", "/bin/sh"].

> Consider another example.  I have some data that need to be
> treated the way M4 treats macro arguments.  That is, the
> string is to be split at commas, and then LEADING white space
> is to be removed but TRAILING white space must NOT be.
>
>   - Problem: this is simply inexpressible.  There is *NO*
>     built-in predicate in section 5.2.1 that can be used to
>     remove leading characters in some set without also
>     removing trailing characters in the same set.

That is indeed true.  No clue how useful this is.  I don't
recall I ever needed this.  I guess the same holds for the
ECLiPSe people.  More below.

> Consider another example.  I have the contents of a file
> as a string.  I want to split it into lines at \n characters
> and to remove trailing white space from each line.   But it
> is important NOT to remove leading white space.  Yes, I have
> real data like this.
>
>   - Problem: this is the reverse of the previous problem.

That sounds like a fair use case.  We could of course solve
this by adding two padding sets to create a split_string/5
or replace PadChars with a term that provides distict
leading and trailing padding.

> Consider another example.  I have a string with fields
> separated by <U+00B7 U+0302> (a middle dot with a circumflex).
> (I actually have some text like that in another window, but
> for some no doubt arcane reason I cannot paste it into a Mail
> window.  I can enter the two codepoints, but Mail will not
> combine them.  Of course, the difficulty of entering the
> separator is one of the *reasons* for choosing it as a separator.)
>
>   - Problem: the documentation of split_string/4 does not make it
>     clear whether separators are 'characters' as the user might
>     perceive them (that is, a base character plus zero or _more_
>     floating diacriticals) or 'codepoints'.  I have a melancholy
>     suspicion that the implementation is not diacritical-aware.

Strings are sequences of code points.  There is a package utf8proc
that will become string aware to realise several of these operations.
I have not yet decided how these will be integrated.

> Consider another family of examples.  I have a lot of data in
> <file> = <record>*
> <record> = <field>*
> format.  Some of it is AWK-style data, where the separator needs
> to be a run of white space and fields can't be empty, as

This works fine (disregarding Unicode white space):

     split_fields(Line, Fields) :-
	split_string(Line, " \t", " \t", Fields).

     ?- split_string(FileString, "\n", "", Lines),
        maplist(split_fields, Lines, Result).

> described above.  Some of it is S-style data, to be read or
> written by the R system.  This needs to deal with numbers
> (_as_ numbers), unquoted words, and quoted strings (which may
> contain any character).  (I have several years worth of data
> about students in another department I should really be analysing
> right now.)  The rest of it is CSV.  In abundance.

Most of this will be fine, except for dealing with quoted strings.
I am not sure about that.  Details for quoted strings vary so much
between languages that I consider that to be too specialized.  There
is library(csv) for reading (and writing) CVS files.  There is another
library for JSON files, XML files, etc.

> In short, I cannot use it to split up the strings I _want_ to
> split up in this kind of way.  The only thing I can do is turn
> the string into a list of codes and then process the list of codes
> in the old familiar way.
>
> split_string/4 is *too specialised*.

I think that the examples above indicate that is not true. It can do the
familar AWK processing. It can do /etc/passwd processing. You can map
strings to numbers (with its problems, such as localization and various
representations used in various languages). The only thing it can not do
is deal with quoted material.

> The Smalltalk analogue is #subStrings:, which is ANSI but violates
> the Smalltalk naming rules.  ("sub" and "strings" are not both whole
> words--the whole word here is "substrings"--so there should be no
> internal capital.  That applies to the SWI documentation as well...)
> In fact my Smalltalk includes 6 variations on that, and the CSV
> parser can make use of _none_ of them.
>
>>   It is fine to read a line, possibly
>> removing leading and trailing white space
>
> Yep, that's one of the problems: leading ***AND*** trailing
> white space.

See above

>> or read a field from a file that uses several delimiters (field, line, ...).
>
> I have case-oriented data that want some kind of quoted string as well.
> (R's read.table() or read.csv().)
> I have numeric data data
>
> Yes, but all of the data I _have_ like that want some kind of
> quoted string as well.
>
> library(read_constant) from Quintus, last revised in 1988
> and still useful:
>	The command read_constant(X)
>	acts much like read(X) would in Pascal.
>	That is, it skips layout in the current input stream,
>	reads a "token", and unifies that with X.
>	There are two kinds of tokens:
>	-- quoted tokens start with ' or ".  They end
>	   with the same character they start with.
>	   ...

I very much have my doubt about this.  You are most likely
in the domain of some data exchange or programming language
and they all differ in the details here: escape the quote
as "" or \", yes or no newlines allowed, allowed escape
sequences, etc. etc.

>	-- simple tokens start with any other character.
>	   They end just before the next layout character
>	   or comma (which is discarded).  These are
>	   returned as numbers if they look like numbers.

This too has its limits.  You may want to distinguish
01 from 1 or 4e5 from 4.0e5 or allow for 4.e5, or not
do floats at all, etc.  If you can split the input into
strings over delimiters, you can map over string_number
or not, depending on the place in the data (e.g., the
column, avoiding agent "007" becoming agent 7).

>	read_constants([X1,...,Xn]) reads n constants
>	and then unifies them with X1,...,Xn after all
>	n have been read.
>
>> All with or without removing (white space) padding.
>
> Unicode 6.3 has 17 Zs characters, 1 Zl, and 1 Zp.
> And that _doesn't_ count CR, LF, TAB, VT, or FF as
> white space, they are all Cc characters.  To name
> the white space characters one has to mention 24
> characters in a string.
>
> But again, this is both *overspecific* -- if I am using
> single-character separators and allowing empty fields the
> odds are that I don't want _any_ trimming -- and
> *underpowered* -- it doesn't allow different trimming
> at each end, it doesn't allow "squishing" internal runs of
> white space to single spaces, it doesn't do a whole lot of
> things, and it requires every field to be split the same
> way.

So, you can do all, except for strip _only_ leading or
_only_ trailing padding, which could be added easily.

> Even Java makes substring creation O(1) time and space,
> so the cleanest thing is to separate splitting (or reading)
> from trimming.
>
> Again, read_string/5 just does too many things; it is both
> overspecific and underpowered.  A starting point might be
>
>	- a predicate to split strings into non-empty fields
>	  at runs of characters in some set (like AWK with
>	  the default field separator)
>	- a predicate to split strings into possibly empty
>	  fields at single instances of characters in some
>	  set (like AWK with a /[...]/ separator)
>	- a predicate to trim a string at either end or both
>	- a predicate to skip characters in a specified
>	  set from a stream
>	- a predicate to read characters in a specified set
>	  from a stream (and leave the next character right
>	  where it was)
>
> So instead of
>	compile_uniset(zs+zl+zp+"\t\n\f", Layout),
>	read_string(Stream, Layout, Layout, Sep, Wanted)
> do
>	compile_uniset(zs+zl+zp+"\t\n\f", Layout),
>	compile_uniset(not(Layout), Non_Layout),
>	uniset_skip(Stream, Layout),
>	uniset_read_string(Stream, Non_Layout, Wanted),
>
> Now _this_ is a building block that is useful in a tokeniser...

Not so sure. You get a non-layout sequence. It is hard to act on
delimiters. For example, using read_string/5 we can implement reading
Name(Arg1, Arg2, ...) using:

my_read_term(In, Term) :-
	read_string(In, "(", " \t\n", _, NameS),
	atom_string(Name, NameS),
	read_string(In, ",)", " \t\n", Del, Arg1),
	(   Del == 0')
	->  (   Arg1 == ""
	    ->	Args = []
	    ;	Args = [Arg1]
	    )
	;   read_args(Del, In, Arg1, Args)
	),
	compound_name_arguments(Term, Name, Args).

read_args(0'), _, Last, [Last]).
read_args(0',, In, Arg, [Arg|T]) :-
	read_string(In, ",)", " \t\n", Del, Arg1),
	read_args(Del, In, Arg1, T).

Which looks pretty reasonable to me.  Turning this into a version
that deals with nested expressions is quite easy too.  The only
small complication is handling the empty argument list case.
(note that there was a bug in read_string/5; the example requires
the git version or next release).

> It really pays for the compiler to execute calls to
> compile_uniset/2 with a known first argument at compile time.

Of course, as I also plan to do for regex.

>> Note that regexes will complete the picture.
>
> For "complete" read "complicate".

Regular expressions are fairly well understood things that are
part of pretty much every standard and language.

>>    We then
>> have the usual stuff:
>>
>>	- split
>>	- select sub string or test for sub string
>>	- finding characters (but only from start end end,
>>           might need a reverse here).
>>	- Get characters at index
>>	- Regex search and replace
>
> This is the 21st century.  We have a character set with over
> 100 000 defined characters.  Many human characters are
> represented by _sequences_ of code-points.  For example,
> after the great CJK unification, now we have a(n arguably
> botched) disunification:  the Ideographic Variation Database.
> Start by reading
> http://babelstone.blogspot.co.nz/2013/01/whats-new-in-unicode-63.html
> Then have a couple of drinks to steady your nerves.
> "Unicode Demystified" only went up as far as Unicode 3.2 -- we really
> need a new edition -- and still ran to 853 pages.  (That's not the
> standard.  That's the simplified introduction.)

Having delimeters as sequences is probably useful to have.  That
is not in your character set approach either.  Regex can of course
do this.

> These days, it really *really* does not make sense to "get
> characters at index."  If you pick up a CJK ideograph and
> DON'T pick up the plane E variant selector with it, and
> then drop it down somewhere else, it will look *wrong*.

That is in general surely true, but there is enough code and
there are enough languages where position picking works nice.
Given that we have the position picking in atoms, you want at
least the same set on strings to simplify porting code that
uses atoms as strings to using strings right away.  Next, you
can consider adding new primitives that handle unicode strings
at a more appropriate level.

> This is, perhaps, the major flaw in the entire string processing
> interface, and *could* be the most compelling argument for
> *having* strings in the language.
>
> Step 1.
>    Given a string, the operation of returning a substring
>    should take O(1) time and O(1) space.

That is likely to happen.  I'm wondering whether or not we
want an interface that can tell us that a string is a substring
at a certain location of another string?

> Step 2.
>    Given a string, split it into the first "character" and
>    the rest of the characters, or fail if it is empty:
>
>	string_first_rest(String, First, Rest)
>	true when String = First++Rest
>	and First ~ (base character)?(diacritical | variant selector)*
>
>    so that you can walk through a string one "character" at a
>    time in a sensible way.  Do something sensible with BIDI
>    state (perhaps by including BIDI flags in the hidden internal
>    substring representation).
>
>    Also provide the other kinds of splitting described in the Unicode
>    standard.

Makes sense (given 1).

>    Oh yeah, there needs to be a
>
>	get_string/[1,2]
>
>    predicate that reads one "character" from (the current|an) input
>    stream and unifies the last argument with it, no matter how many
>    code-points are involved.

Also makes sense, although the name seems a bit misleading to me.
It does require advanced Unicode processing though, and that is not
something I see happen anytime soon unless someone is willing to do
it.

> Ordinary programmers don't have a hope in the hot place of
> getting this right, *especially* if they are seduced into working
> with one code point at a time by giving them only an antique
> interface.
>
> As an ordinary programmer, I have been _trying_ to put some of
> this stuff into my Smalltalk, and it's insanely difficult.
> Getting BIDI stuff right is arg weeble weeble and then they go
> and revise the BIDI algorithm...  Yes, it means that if you
> want to read strings from a stream *PROPERLY* you need to maintain
> BIDI state in the stream object.
>
> U+2068: FIRST STRONG ISOLATE
> U+2069: POP DIRECTIONAL ISOLATE
>
> ?  That scratching sound is me trying to climb the walls...
> "This is reality.  It doesn't have to make sense."
>>
>> And there is library(pure_input) to process files using
>> DCGs.
>
> Which is a good thing.  One thing I will note is that it
> if strings are going to be in the language, it would be
> well if DCGs worked on strings, not just allowing string
> literals, but working *on* strings as data.

It is not very hard to use the same technique as library(pure_input)
does on files to create a `lazy list' from a string, especially if
we have O(1) substrings.

>> As you already invested some time, what precisely do we miss?
>
> Unicode?
>
> Unicode is *horrifyingly* complex and is only getting worse.
> Too much thinking about it and you get Krantzberg syndrome.
> (http://www.tor.com/stories/2008/07/down-on-the-farm)

For the moment, the only Unicode things I'd like to solve at the core
level is representing Unicode strings and most likely get access to the
general classification of Unicode characters. I also want an efficient
interface to access strings as UTF-8 from C, so you can use the foreign
interface to add Unicode string facilities easily. I need that for regex
to start with. One of the issues is that strings are relocated if GC is
performed.  This should be resolved either through some kind of handle
or moving them out of the stack if we want handles on them and use GC
to collect them again.

That should give the interfaces that you need to get things done. The
rest can be added on `as-needed' basis.

Thanks for the comments. Despite your opening, I don't see that much
wrong with what there is now. I think I've showed that split_string/4
and read_string/5 are sensible. We could consider two padding arguments
or a term for the padding argument that allows for specifying different
leading and trailing padding.  All the rest can be added step-by-step.

That is the way SWI-Prolog has evolved for over 25 years: don't try to
solve it all in one go, but take it step-by-step as requirements show
up. First of all, I've far too few braincells to do it all properly in
one step. Second, nothing would become available within a reasonable
time frame and last, I need to squeeze Prolog development between other
obligations. These other obligations provide many of the requirements,
but time constraints do not allow solving it all perfectly right now.
All I want to do is avoiding steps that make it impossible to do it
properly later without breaking a lot (especially for the users). So
far, dispite I sometimes come to the conclusion I took a wrong
decision in the past and the next step now results in redoing the
previous one or living with a suboptimal solution, this has worked
pretty well.

	Cheers --- Jan

P.s.	Considering characters, I sense some motivation to use
	atoms rather than code points, so you can represent a
	character with its (diacritical | variant selector*).
	Right?

	Version 7 could be the right time to make that migration
	as well.  Some people are surely in favor of this.  I'm
	only afraid of the implications.  If anyone sees a good
	route, please share it.  I was considering a new type,
	with numeric properties, but that seems wrong (now).