q-lang-users

[q-lang-users] Association lists

[Jiri S. <jir...@bl...>]

Hello Q users,

I have ported and completed the association lists based on AVL trees 
from the SWI-Prolog to Q. Enclosed you will find the dict.q rewritten to 
use this algorithm. It is not as elegant as the current implementation 
(it is rather tricky), but the tree updates are more than two times 
faster for large dictionaries.

Enjoy.

Jiri

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Hi Jiri,

that looks nice, thanks a lot. Do you have a sf.net account? Then I
could give you wiki access so that you can upload and describe it there.

Indeed your implementation seems to be much faster than the one in the
standard library (which was based on Bird/Wadler). Care to elaborate on
the implementation tricks that make this happen? Maybe we should redo
bag, set and hdict, too, and replace the stdlib implementations...

Albert

Jiri Spitz wrote:
> I have ported and completed the association lists based on AVL trees
> from the SWI-Prolog to Q. Enclosed you will find the dict.q rewritten to
> use this algorithm. It is not as elegant as the current implementation
> (it is rather tricky), but the tree updates are more than two times
> faster for large dictionaries.

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [q-lang-users] Association lists

[Eddie R. <ed...@ri...>]

Great! I use those libraries very often. Making those libraries faster 
would definitely improve the execution of most (all?) of my programs.

Thanks Jiri!

Eddie Rucker

Albert Graef wrote:
> Hi Jiri,
> 
> that looks nice, thanks a lot. Do you have a sf.net account? Then I
> could give you wiki access so that you can upload and describe it there.
> 
> Indeed your implementation seems to be much faster than the one in the
> standard library (which was based on Bird/Wadler). Care to elaborate on
> the implementation tricks that make this happen? Maybe we should redo
> bag, set and hdict, too, and replace the stdlib implementations...
> 
> Albert
> 
> Jiri Spitz wrote:
>> I have ported and completed the association lists based on AVL trees
>> from the SWI-Prolog to Q. Enclosed you will find the dict.q rewritten to
>> use this algorithm. It is not as elegant as the current implementation
>> (it is rather tricky), but the tree updates are more than two times
>> faster for large dictionaries.
> 

Re: [q-lang-users] Association lists

[Jiri S. <jir...@bl...>]

Albert Graef napsal(a):
> that looks nice, thanks a lot. Do you have a sf.net account? Then I
> could give you wiki access so that you can upload and describe it there.

I have already created the ID and sent you an e-mail. I'll try to 
describe the algorithm there.

>Maybe we should redo bag, set and hdict, too, and replace the stdlib implementations...

You will find them all enclosed. I tested them with a lot of both 
sequential and random updates and they seem to work. Of course, some 
testing in working applications would be appreciated.


Regards,

Jiri

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Jiri Spitz wrote:
> You will find them all enclosed.

Thanks, that was quick. :) Great piece of work! One suggestion, though:
Would it be possible to reformat the sources so that they fit into 80
columns? I'd very much appreciate that, since I frequently read these
files as documentation, sometimes on devices with small displays.

Also, it might be appropriate to add a link to SWI-Prolog to your
comment at the beginning of the files.

> I tested them with a lot of both
> sequential and random updates and they seem to work. Of course, some
> testing in working applications would be appreciated.

I'll probably do another release candidate so that everybody can give it
a shot before the official 7.11 release. I have plenty of programs
making heavy use of these data types, so I hope that most kinds of bugs
would be shaken out pretty quickly.

Cheers,
Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [q-lang-users] Association lists

[Jiri S. <jir...@bl...>]

Albert Graef napsal(a):

> Would it be possible to reformat the sources so that they fit into 80
> columns? I'd very much appreciate that, since I frequently read these
> files as documentation, sometimes on devices with small displays.

It is now reformatted. I hope the code is still reasonably readable and 
that I didn't introduce any error.

> Also, it might be appropriate to add a link to SWI-Prolog to your
> comment at the beginning of the files.

Good idea - done.

Regards,

Jiri

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Jiri Spitz wrote:
> It is now reformatted. I hope the code is still reasonably readable and
> that I didn't introduce any error.

Ok, thanks a lot. I did some more reformatting so that the layout is
more in line with the rest of the library, and fixed a couple of minor
bugs and typos. I also removed the do/map stuff in dict.q (while this
might be useful, I'd prefer the new version to be a drop-in replacement
for the old one for now). It is in cvs now.

There's still a minor issue with the inserta/deletea operations,
however. The problem is that you used syntactic equality (foo X X = ...)
rather than (=) to decide equality of two key values. That will be ok in
most cases (hdict should be fine as the real key there is always an
integer), but for dict/bag/set you don't know what the actual key type
is, it may be *any* ordered type, and some key types might well use a
version of (=) which goes beyond simple syntactic equality, see
"Non-Linear Equations" in the manual
[http://q-lang.sourceforge.net/qdoc/qdoc_7.html#SEC42] for an explanation.

I'll try to fix this (shouldn't be too difficult) and give it a first
test drive with a couple of my programs. If that works ok I'll upload a
new release candidate later today.

Cheers,
Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [q-lang-users] Association lists

[Jiří S. <jir...@bl...>]

Albert Graef wrote:
> Ok, thanks a lot. I did some more reformatting so that the layout is
> more in line with the rest of the library, and fixed a couple of minor
> bugs and typos. I also removed the do/map stuff in dict.q (while this
> might be useful, I'd prefer the new version to be a drop-in replacement
> for the old one for now). It is in cvs now.

OK.

> There's still a minor issue with the inserta/deletea operations,
> however. The problem is that you used syntactic equality (foo X X = ...)
> rather than (=) to decide equality of two key values. That will be ok in
> most cases (hdict should be fine as the real key there is always an
> integer), but for dict/bag/set you don't know what the actual key type
> is, it may be *any* ordered type, and some key types might well use a
> version of (=) which goes beyond simple syntactic equality, see
> "Non-Linear Equations" in the manual
> [http://q-lang.sourceforge.net/qdoc/qdoc_7.html#SEC42] for an explanation.
> I'll try to fix this (shouldn't be too difficult) and give it a first
> test drive with a couple of my programs. If that works ok I'll upload a
> new release candidate later today.

I see, you are right.

However I fall in problems when using my libraries together. Whether it 
works depends on the order in which I import them

Eg. if I do

import set, dict;

then I receive this conversation:

==> insert emptydict (1,1)
fst (set::inserta (dict []) (1,1))

and even with qualified call

==> dict::insert emptydict (1,1)
fst (set::inserta (dict []) (1,1))

When I change the import order, ten it is OK:

import dict, set;

==> insert emptydict (1,1)
dict [(1,1)]

==> insert emptyset 1
set [1]

Other two libraries behave similarly. I cannot find any bad declarations 
(eg. public instead of private). This may be related to the fact, that 
my versions of inserta have different arity for dict and set while your 
corresponding functions have the same arity.


BTW I was a bit surprised, that this works:

==> set::inserta emptyset 1
(set [1],true)

I wuould expect, that private functions are not accesible at all, but 
this may be an intention.

Regards,

Jiri

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Jir(í Spitz wrote:
> However I fall in problems when using my libraries together. Whether it 
> works depends on the order in which I import them

That was one of the bugs I fixed. (You forgot the type guards on the
insert/delete interface functions, so the wrong equation would be
invoked.) Get the latest versions from cvs, they should be ok (except
for the key comparison issue, I still have to fix that one).

Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [q-lang-users] Association lists

[Jiří S. <jir...@bl...>]

Albert Graef wrote:
> That was one of the bugs I fixed. (You forgot the type guards on the
> insert/delete interface functions, so the wrong equation would be
> invoked.) Get the latest versions from cvs, they should be ok.
.....
 >
 > Moreover, to facilitate testing and debugging, in the interpreter it
 > is possible to gain access to all public and private symbols of the
 > program (also in modules not directly imported in the main script)
 > using qualified identifiers.

I didn't read the docs with appropriate attention... :-(

Nonetheless, I discovered another small bug. In dict and similarly hdict 
should be

update D:Dict (X, Y) = insert D (X,Y);
or
update D:Dict XY = insert D XY;

instead of

update D:Dict X Y = insert D (X,Y);

Regards,

Jiri

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Jir(í Spitz wrote:
> Nonetheless, I discovered another small bug. In dict and similarly hdict 
> should be
> 
> update D:Dict (X, Y) = insert D (X,Y);
> or
> update D:Dict XY = insert D XY;
> 
> instead of
> 
> update D:Dict X Y = insert D (X,Y);

Nope, update takes three args, see stddecl.q. Citing the manual:

 update D X Y

    same as insert D (X,Y)

I.e., for dictionaries update is just a completely curried form of
insert. Has always been that way.

Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [q-lang-users] Association lists

[Jiri S. <jir...@bl...>]

Albert Graef wrote:
> Nope, update takes three args, see stddecl.q. Citing the manual:
> 
>  update D X Y
> 
>     same as insert D (X,Y)
> 
> I.e., for dictionaries update is just a completely curried form of
> insert. Has always been that way.

You convinced me, thanks for your patience.

I have corrected the issue with key comparisons in dict, set and bag. 
You will find them enclosed.

Jiri

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Jiri Spitz wrote:
> I have corrected the issue with key comparisons in dict, set and bag.
> You will find them enclosed.

Hmm, I already have that in cvs. Would you mind going over my version to
see if it's ok with you? You can find it at
http://q-lang.cvs.sourceforge.net/q-lang/q/stdlib/

Albert

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [q-lang-users] Association lists

[Jiří S. <jir...@bl...>]

Albert Graef wrote:
> Hmm, I already have that in cvs. Would you mind going over my version to
> see if it's ok with you? You can find it at
> http://q-lang.cvs.sourceforge.net/q-lang/q/stdlib/

I thought that you put there my versions because they are bytewise 
identical.

 > I also corrected a missing arg in hdict::deletea.

Thanks.

Jiri

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Jir(í Spitz wrote:
> I thought that you put there my versions because they are bytewise 
> identical.

Coincidence. :)

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Jir(í Spitz wrote:
> BTW I was a bit surprised, that this works:
> 
> ==> set::inserta emptyset 1
> (set [1],true)
> 
> I wuould expect, that private functions are not accesible at all, but 
> this may be an intention.

http://q-lang.sourceforge.net/qdoc/qdoc_4.html#SEC19

"Moreover, to facilitate testing and debugging, in the interpreter it is
possible to gain access to all public and private symbols of the program
(also in modules not directly imported in the main script) using
qualified identifiers."

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag

Re: [q-lang-users] Association lists

[Albert G. <Dr....@t-...>]

Albert Graef wrote:
> I'll try to fix this (shouldn't be too difficult) and give it a first
> test drive with a couple of my programs. If that works ok I'll upload a
> new release candidate later today.

Ok, the key comparisons are fixed now, and I also corrected a missing
arg in hdict::deletea. Looks good so far! RC3 is on its way, stay tuned...

-- 
Dr. Albert Gr"af
Dept. of Music-Informatics, University of Mainz, Germany
Email:  Dr....@t-..., ag...@mu...
WWW:    http://www.musikinformatik.uni-mainz.de/ag