ANN: VivoMind Prolog Unicode Resources released

[Paulo Moura]

Hi,

The Prolog Unicode 6.2 resources developed by VivoMind LLC are now
available as public domain software at:

https://github.com/VivoMind

The VivoMind Prolog Unicode Resources are a set of plain Prolog files
resulting from the conversion of most (but not all) official UCD 6.1
files and updated for the changes in the 6.2 standard. A set of
auxiliary predicates is also included to simplify using the provided
tables of code point properties. Some of the original data was split
in individual files per code point property to make it easier to load
only the resources required by a specific application.

Enjoy,

Arun Majumdar
Paulo Moura

[Jan Burse]

Hi,

What do you do against a full predicate
scan in the following query:

unicode_core_property(CodePoint, Property) :-
( var(CodePoint) ->
% generate code point pairs
unicode_core_property(CodePointStart, CodePointEnd, Property),
between(CodePointStart, CodePointEnd, CodePoint)
; % try first-argument indexing first
unicode_core_property(CodePoint, _, CodePointProperty) ->
Property = CodePointProperty
; % look for a code point range that includes the given code point
unicode_core_property(CodePointStart, CodePointEnd, CodePointProperty),
between(CodePointStart, CodePointEnd, CodePoint) ->
Property = CodePointProperty
).

https://raw.github.com/VivoMind/unicode_data/master/unicode_derived_core_properties.pl

For example a query:

?- unicode_core_property(0x2F801, X).

will eat quite a lot of CPU.

Bye

Paulo Moura schrieb:

[Paulo Moura]

On Apr 27, 2:24 pm, Jan Burse <janbu...@fastmail.fm> wrote:
> Hi,
>
> What do you do against a full predicate
> scan in the following query:
>
> unicode_core_property(CodePoint, Property) :-
> (       var(CodePoint) ->
>         % generate code point pairs
>         unicode_core_property(CodePointStart, CodePointEnd, Property),
>         between(CodePointStart, CodePointEnd, CodePoint)
> ;       % try first-argument indexing first
>         unicode_core_property(CodePoint, _, CodePointProperty) ->
>         Property = CodePointProperty
> ;       % look for a code point range that includes the given code point
>         unicode_core_property(CodePointStart, CodePointEnd, CodePointProperty),
>         between(CodePointStart, CodePointEnd, CodePoint) ->
>         Property = CodePointProperty
> ).
>

> https://raw.github.com/VivoMind/unicode_data/master/unicode_derived_c...

>
> For example a query:
>
> ?- unicode_core_property(0x2F801, X).
>
> will eat quite a lot of CPU.

RTFM:


Usage
-----
Most applications only require some of the tables present in these
resources.
Most of these tables define properties for ranges of code points and
not for
single code points but the provided auxiliary predicates allow access
for a
single code point. When increased performance is required, consider
using the
existing tables and auxiliary predicates to generated derived tables
more fit
for your specific application.

Cheers,

Paulo

[Jan Burse]

Paulo Moura schrieb:

> Most applications only require some of the tables present in these resources.
> Most of these tables define properties for ranges of code points and not for
> single code points but the provided auxiliary predicates allow access for a
> single code point. When increased performance is required, consider using the
> existing tables and auxiliary predicates to generated derived tables more fit
> for your specific application.

Did somebody already create such "derived tables"?
What was the algorithm/strategy?

Bye

P.S.: This one uses a trie:
http://javasourcecode.org/html/open-source/jdk/jdk-6u23/sun/text/normalizer/UCharacter.html

[Paulo Moura]

On Apr 27, 4:47 pm, Jan Burse <janbu...@fastmail.fm> wrote:
> Paulo Moura schrieb:
>
> > Most applications only require some of the tables present in these resources.
> > Most of these tables define properties for ranges of code points and not for
> > single code points but the provided auxiliary predicates allow access for a
> > single code point. When increased performance is required, consider using the
> > existing tables and auxiliary predicates to generated derived tables more fit
> > for your specific application.
>
> Did somebody already create such "derived tables"?

Yes. Several times.

> What was the algorithm/strategy?

Whatever fits best a specific application? Creating derived tables is
not exactly rocket science. More like Prolog 101.

[Jan Burse]

Paulo Moura schrieb:

>> Did somebody already create such "derived tables"?
> Yes. Several times.
>
>> >What was the algorithm/strategy?
> Whatever fits best a specific application?

What would be a solution to the following application,
i.e. querying the predicate unicode_core_property/2 with
the first argument bound?

Jan Burse wrote, 15:24:

> For example a query:
>
> ?- unicode_core_property(0x2F801, X).

Best Regards

[Paulo Moura]

Your application is calling a provided auxiliary predicate with the
first argument bound? Really? That's it? Nothing more? What's the
point?

Do you have anything of value to contribute to the announcement? I.e.
besides being rude by renaming someone else thread? You present
yourself publicly as the implementer of a commercial Prolog system. Do
you really need me (or anyone else) to tell you how to cache and reuse
the solutions to a predicate?

[Jan Burse]

Paulo Moura schrieb:

> you really need me (or anyone else) to tell you how to cache and reuse
> the solutions to a predicate?

Caching, tabling, memoizing would be one solution. But such
a solution would assume some locality. I am not sure whether
this can be assumed.

For example unicode_core_property/2 could possibly be used
to implement a parser. To delimit tokens inside a text.
But this text need not use a small set of characters
repetetively.

Would caching make it fast enough, i.e. is this again
something feasible or not? What is the evidence?

How is caching related to what is written on GitHub?
Paulo Moura wrote, 27.04.13 15:44

> When increased performance is required, consider using the
> existing tables and auxiliary predicates to generated
> derived tables more fit for your specific application.

Derived tables is not the same as caching. What was
on the mind of the writer, when he said derived
tables?

Bye

[Jan Burse]

Jan Burse schrieb:

>
> Caching, tabling, memoizing would be one solution.

Not really synonymous, for a cache I assume that
it has a bounded size. Tabling and memoizing need
not have a size limit.

Implementing a bounded size cache in Prolog is
not that trivial. How do you expel for example
the oldest element, when a new element arrives?

Tabling, memoizing on the other hand with
unbounded size is a little simpler, especially
for single valued functions.

If your predicate is multi valued, then
tabling, memoizing is less trivial. Especially
under concurrent access.

unicode_core_property/2 with the first argument

bound is multi valued in the second argument. Means
a call can generate multiple solutions, for
example we have:

?- unicode_core_property(0x0061,X).
X = 'Alphabetic' ;
X = 'Lowercase'

Bye

[Paulo Moura]

On Apr 28, 2:35 am, Jan Burse <janbu...@fastmail.fm> wrote:
> Jan Burse schrieb:
>
>
>
> > Caching, tabling, memoizing would be one solution.
>
> Not really synonymous, for a cache I assume that
> it has a bounded size. Tabling and memoizing need
> not have a size limit.
>
> Implementing a bounded size cache in Prolog is
> not that trivial. How do you expel for example
> the oldest element, when a new element arrives?
>
> Tabling, memoizing on the other hand with
> unbounded size is a little simpler, especially
> for single valued functions.
>
> If your predicate is multi valued, then
> tabling, memoizing is less trivial. Especially
> under concurrent access.

http://en.wikipedia.org/wiki/K.I.S.S.

> unicode_core_property/2 with the first argument
> bound is multi valued in the second argument. Means
> a call can generate multiple solutions, for
> example we have:
>
>     ?- unicode_core_property(0x0061,X).
>     X = 'Alphabetic' ;
>     X = 'Lowercase'

Did you also noticed in the documentation:

* File:
`unicode_core_properties.pl`
* Provides:
`unicode_math/1-2`
`unicode_alphabetic/1-2`
`unicode_lowercase/1-2`
`unicode_uppercase/1-2`
`unicode_cased/1-2`
`unicode_case_ignorable/1-2`
`unicode_changes_when_lowercased/1-2`
`unicode_changes_when_uppercased/1-2`
`unicode_changes_when_titlecased/1-2`
`unicode_changes_when_casefolded/1-2`
`unicode_changes_when_casemapped/1-2`
`unicode_id_start/1-2`
`unicode_id_continue/1-2`
`unicode_xid_start/1-2`
`unicode_xid_continue/1-2`
`unicode_default_ignorable/1-2`
`unicode_grapheme_extend/1-2`
`unicode_grapheme_base/1-2`
`unicode_grapheme_link/1-2`
* Dependencies:
files in the `unicode_core_properties` directory

[Paulo Moura]

http://www.red-sweater.com/blog/1078/open-source-obligations

[Jan Burse]

Paulo Moura schrieb:

The problem with the predicates in these already derived
files, is that they share the same design as the predicate
unicode_core_property/2. I.e. they are subject to a
full predicate scan for some characters.

For example when I look at the predicate unicode_alphabetic/1
I see the following design:

unicode_alphabetic(CodePoint) :-

( var(CodePoint) ->
% generate code point pairs

unicode_alphabetic(CodePointStart, CodePointEnd),

between(CodePointStart, CodePointEnd, CodePoint)
; % try first-argument indexing first

unicode_alphabetic(CodePoint, _) ->
true

; % look for a code point range that includes the given code point

unicode_alphabetic(CodePointStart, CodePointEnd),
between(CodePointStart, CodePointEnd, CodePoint) ->
true
).

https://github.com/VivoMind/unicode_data/blob/master/unicode_core_properties/unicode_alphabetic.pl

So when I would for example ask:

?- unicode_alphabetic(0x2F801)

will eat quite a lot of CPU.

So these files don't change not much, they don't
mitigate the problem.

Bye

[Jan Burse]

Paulo Moura schrieb:

>> >Derived tables is not the same as caching. What was
>> >on the mind of the writer, when he said derived
>> >tables?
> http://www.red-sweater.com/blog/1078/open-source-obligations

Since this is comp.lang.prolog, others are welcome
to share their thoughts.

I don't think posts like the above have anything
to do with my question, which is not tied to some
particular software, published in some particular
repository under some particular license.

Jan Burse wrote, 27.04.13 17:47:

> Did somebody already create such "derived tables"?

> What was the algorithm/strategy?

> P.S.: This one uses a trie:
> http://javasourcecode.org/html/open-source/jdk/jdk-6u23/sun/text/normalizer/UCharacter.html

I am really curious how a solution would overcome
some limitations of Prolog. For example a typical
Prolog does not build indexes that allow range based
queries to be quickly processed.

On the other hand most relational database can
easily work with queries of the form:

select *
from table
where col > const

They can use an index to fetch all elements that
are above const. In Prolog there is already a
problem of formulation:

p(X), X>const

The information X>const comes to late. I guess
these Prolog inherent problems automatically
come up when transforming relational database
solutions into Prolog.

So the problem is by way not trivial, and I
really wonder what a good efficient solution
would look like.

Bye

[Jan Burse]

Jan Burse schrieb:

>
> So these files don't change not much, they don't
> mitigate the problem.

These files are also not necessary in a Prolog
system with multi-argument indexing, such
as SWI-Prolog, Jekejeke Prolog, etc..

I guess a query

?- unicode_core_property(0x2F801, 'Alphabetic').

will do the same as:

?- unicode_alphabetic(0x2F801).

But this wouldn't be a great progress, except
that a couple of files can be spared. The problem
of a full predicate scan persists with multi-
argument indexing.

Bye

[Paulo Moura]

On Apr 28, 8:15 am, Jan Burse <janbu...@fastmail.fm> wrote:
> Paulo Moura schrieb:
>
> >> >Derived tables is not the same as caching. What was
> >> >on the mind of the writer, when he said derived
> >> >tables?
> >http://www.red-sweater.com/blog/1078/open-source-obligations
>
> Since this is comp.lang.prolog, others are welcome
> to share their thoughts.

Take a hint. Stop acting like the proverbial panhandler in that blog.

> I don't think posts like the above have anything
> to do with my question, which is not tied to some
> particular software, published in some particular
> repository under some particular license.

Really? You rename someone else ANNOUNCEMENT (with a void question,
btw), about particular software, published in a particular repository
under a repository license (actually, PUBLIC DOMAIN). And your
questions are all about how the GIFTED code in that software is
problematic for you while ignoring its philosophy and the suggestions
in the documentation. The release is essentially a set of DATA files
but you seem unable to get past some interface predicates that you
find inadequate for some (as always with you) secret application.

I ask again, what's your contribution here besides the noise? Others
have already contributed elsewhere with suggestions and bug reports
that resulted in improvements to these resources. Those improvements
are already in the public repository, btw.

[Paulo Moura]

On Apr 28, 8:24 am, Jan Burse <janbu...@fastmail.fm> wrote:
> Jan Burse schrieb:
>
>
>
> > So these files don't change not much, they don't
> > mitigate the problem.
>
> These files are also not necessary in a Prolog
> system with multi-argument indexing, such
> as SWI-Prolog, Jekejeke Prolog, etc..

The released resources are Prolog-agnostic.

> I guess a query
>
> ?- unicode_core_property(0x2F801, 'Alphabetic').
>
> will do the same as:
>
> ?- unicode_alphabetic(0x2F801).
>
> But this wouldn't be a great progress, except
> that a couple of files can be spared. The problem
> of a full predicate scan persists with multi-
> argument indexing.

And you contribution to the progress is?

The `unicode_alphabetic.pl` defines a table with 855 clauses, each one
defining a code point range. These clauses declare the alphabetic
Unicode property for *102159* code points. Thus, creating a derived
table with one clause per code point will go from 855 clauses to
102159 clauses with access becoming O(1).

Waiting your contribution for a (Prolog-agnostic) solution with better
space and time performance within the interval of the two solutions
above.

[burs...@gmail.com]

The issue is that the 800 clauses solution shouldn't be the
lower bound. There should be solutions outside of the interval,
below it concerning time complexity.

I do not intend to contribute right now. I am only asking whether
somebody did something in this direction. Of course a good
tradeoff between space and time is desired.

[Paulo Moura]

On Apr 28, 10:04 pm, burse...@gmail.com wrote:
> The issue is that the 800 clauses solution shouldn't be the
> lower bound. There should be solutions outside of the interval,
> below it concerning time complexity.

Shouldn't be the lower bound? There are 855 code point range intervals
for the alphabetic property. Assuming no errors in the official
Unicode file, no two of those intervals are contiguous. So, how do you
"compress" a *set* of code ranges in order to use less clauses? And
without paying a significant time penalty for accessing the compressed
form (assuming that a practical one exists, of course)?

> I do not intend to contribute right now.

I knew that from the beginning. But that's nice of you confirming it.
If and when you have something to contribute, you're welcome to visit
the GitHub repository, fork it, code your improvements, and issue a
pull request.

> I am only asking whether
> somebody did something in this direction. Of course a good
> tradeoff between space and time is desired.

And the best way you have to ask that question is a silly rename of
the announcement thread to "Feasible?" Feasibility of the released
DATA files, even of the provided auxiliary predicates, DEPENDS on the
specifics of the APPLICATION where you intend to use them. What
constitutes a good tradeoff DEPENDS on the specifics of the
APPLICATION where you intend to use them.

[burs...@gmail.com]

Hi,

> lower bound or not?
I wrote 'time complexity'. I don't think the way you deal
with the intervals is time optimal. But possibly the space
can be also reduced.

You should also look at the time complexity of character
classification misses in your derived files. How long does
it take to detect that something is not alphabetic?

> notion of feasiblity
Using the term feasible is appropriate if the 'time
complexity' is prohibitive for certain applications.
Your solution is sure prohobitive for certain
applications.

Take for example an intenationalized prolog
interpreter which would use an O(n) character
classifier. I would need to wait for ages to load
my files, which are now loaded in a blink.

Bye

P.S.: You might continue insulting me with
things such as RTFM, rude, silly, etc.. Maybe
you should go see a doctor, it seems that you
have some serious mental problems.

[Torsten Eichstädt]

> P.S.: You might continue insulting me with
> things such as RTFM, rude, silly, etc.. Maybe
> you should go see a doctor, it seems that you
> have some serious mental problems.
>

I have problems to distinguish rational from emotional arguments in this
newsgroup...

You do not need to help me by enumerating the two sets, but maybe by just
trying to change your habits. "Feasible" applies here, too.

Thanx in advance!
--
=|o)

[Paulo Moura]

On Apr 30, 7:26 am, burse...@gmail.com wrote:
> Hi,
>
> > lower bound or not?
>
> I wrote 'time complexity'. I don't think the way you deal
> with the intervals is time optimal. But possibly the space
> can be also reduced.

Again, these are data files. From the documentation: "The VivoMind
Prolog Unicode Resources are a set of files resulting from the

conversion of most (but not all) official UCD 6.1 files and updated

for the few changes in the 6.2 standard."

> You should also look at the time complexity of character
> classification misses in your derived files. How long does
> it take to detect that something is not alphabetic?

"You should also" really sums it all. Note that those "derived files",
as you can notice in their headers, are derived by the Unicode
consortium, not be me.

> > notion of feasiblity
>
> Using the term feasible is appropriate if the 'time
> complexity' is prohibitive for certain applications.
> Your solution is sure prohobitive for certain
> applications.

Sigh. Not my solution. Not any solution, in fact. Again, these are
data files from the Unicode consortium directly translated to Prolog.
So much should be clear at a glance to the files themselves or the
documentation.

> Take for example an intenationalized prolog
> interpreter which would use an O(n) character
> classifier. I would need to wait for ages to load
> my files, which are now loaded in a blink.

That sound like you have something that you could but are not willing
(yet? ever?) to contribute.

> P.S.: You might continue insulting me with
> things such as RTFM, rude, silly, etc.. Maybe
> you should go see a doctor, it seems that you
> have some serious mental problems.

If you fell insulted by people driving your attention to the way you
behave in this newsgroup, consider changing your ways. For example,
you had so far a dozen opportunities to restore the original thread
subject. Or to read the (short) documentation so that I don't have (as
again above) keep citing it. Or to make a contribution to improve
these gifted resources. It's not that I'm the only one in this
newsgroup annoyed with your posture.

[burs...@gmail.com]

The positive case is when the predicate succeeds. For ascii and latin
You might have practically O(1), since the intervals are at the beginning.

The negative case us wben the predicate fails. For any encoding
You have O(n). With or without multi-argument indexing.

The negative case is quite common in parsing. For example
Consider the following identifier syntax:

Ident = alpha { alpha | digit }

A typical implementation will have a negative test when the remainder
Of an identifier has been scanned.

So if you have the following input text:

a+a+a+...

The scanner will spend 50% of the time with full predicate scan.

Now you can continue interfering with my question which reads
As follows:

- is there somebody around who has succesfully takled this
Problem and built a better implementation?

- the question doesnot exclude that it might be derived
By P.M. library, but this is not the real issue here.

- also i understand the aim and limitation of P.M.
Library here, but this is not the real issue here.

Bye

[burs...@gmail.com]

> A typical implementation will have a negative test
> when the remainder Of an identifier has been scanned.

I guess with some state machine technique and some
Cuts the problem can be slightly mitigated, at least
For ascii and latin. But for the cut to work the properties
Have to be ordered according to the scanner. Ugly.

[burs...@gmail.com]

> That sound like you have something that you
> could but are not willing (yet? ever?) to contribute.

There is nothing on my side that i could contribute
Right now. There is no necessety to implement
A prolog token scanner that is capable of unicode
To implement in Prolog itself.

You can use any programming language for that
Purpose, i.e C, Ada, Java, etc..

I already posted a link to the IBM UCharacter class
Implementation in Java. If you follow the link you
Find the source code. It seems that it uses a trie
As i already mentioned.

There is also the Oracle Character class, and for
Prolog scanners it turns out that the Character type
Is also handy to implement Prolog scanners. The
Jekejeke Unicode dealing is documented based
On character types, and not properties.

Oracle Character class provides an interesting
Implementation since the different planes are
Implemented as instances of classes possibly
Derived from a base class.

So different planes can use different algorithms/
Strategies if desired. This is at least what i saw
The last time i inspected the source. Also derived
Classes and their data are dynamically autoloaded
When first needed.

Adopting this OO design would make a nice Logtalk
Project.

[burs...@gmail.com]

> Oracle Character class provides an interesting
> Implementation since the different planes are
> Implemented as instances of classes possibly
> Derived from a base class.

I guess i had a look at OpenJDK:
http://en.m.wikipedia.org/wiki/OpenJDK

Can provide a more exact ref if desired.

[Jan Burse]

Paulo Moura schrieb:

> in the documentation. The release is essentially a set of DATA files
> but you seem unable to get past some interface predicates that you
> find inadequate for some (as always with you) secret application.

Actually the applications of Unicode are numerous. So it
should be plural applications and not singular application.
Here is a little excerpt:

- Parsing Prolog Texts: Enlarged classes based on Unicode
for the character classes already found in the ISO core
standard syntax definition. Including numerals in foreign
scripts such as arabic, etc.. See also:
http://www.unicode.org/reports/tr31/

- Unparsing Prolog Terms: Automatically detecting whether
an atom needs to be quoted, according to the enlarged
syntax definition.

- Breaking a Natural Language Text into Words: Algorithms
based on property pairing. See also:
http://www.unicode.org/reports/tr29/

- Breaking a Pattern for Natural Language Text Search:
Again algorithms based on property pairing, but this
time to break the pattern that is matched.

- Ignoring Case during Pattern Matching: Comparing characters
by ignoring the case. See also:
http://www.unicode.org/faq/casemap_charprop.html

- What else?

I guess the above applications are no secret at all, and
not extremely difficult to implement pragmatically.

Also they are already predicted by the tech docs of Unicode
itself. And all the applications only work with O(1) unicode
operations. Otherwise they become infeasible.

Best Regards