Re: [ERROR] fedora 17 install error
Hi, On Sat 09 Jun 2012 05:01, B.Tag bb.q...@gmail.com writes: ok. i system environmental path included chinese.compile time it does not understand Chinese. Interesting! I'm happy it worked for you, but I am curious what the precise error was. Which environment variable caused the build to fail? Thanks, Andy -- http://wingolog.org/
Growable arrays?
Hi, the main data structure of Lua is a table, an associative array, and a table t has a continguous numerically addressed part from 1..#t, with all other indices going through a hashing mechanism. One principal distinguishing feature, like with a Scheme hashtable, is the ability to grow on-demand. Scheme/Guile vectors are fixed size. Now I have a situation where I have a basic type lattice with records stored in vectors, and this type lattice may be extended dynamically (which typically happens at the start of a whole file, for potentially multi-file runs). Scheme does not offer a suitable data structure for that. It is a bit of a nuisance that one can grow a hashtable efficiently and on-demand, but not so an array. Now it would be possible when the type lattice gets extended to store the new entries in a hashtable and go from there. Or put them into a list, and reallocate on first access beyond the existing element. That seems rather contorted. And since there is, if I remember, a project to run Lua on top of Guile, having a fundamental and reasonably efficient data structure corresponding to a Lua table, or at least the contiguous part of a Lua table, would seem like a reasonably useful idea. After all, there already _is_ such a mechanism underlying hash tables so it seems somewhat peculiar not to have it available for vectors as well. Suggestions? -- David Kastrup
subbytevectors
Hi, It would be very convenient to offer bytevectors that give a view on some other data structure, possibly another bytevector. We already have that, to an extent, with pointer-bytevector. We can consecrate that with some subbytevector facility. I think it's a good idea but it has some costs. One is that currently, in the R6RS bytevector specification, one bytevector cannot alias another. This knowledge can allow the optimizer to do more things. Another point is that since Guile can control the allocation of bytevectors, it can ensure their alignments, and so compile e.g. a (bytevector-u32-ref bv 12 (native-endianness)) to an efficient access, knowing that it is aligned. If we offer subbytevectors, this won't be possible in general. Again, the gain in expressiveness is probably worth it, but I wanted to put the question out there to see if anyone has an opinion. Regards, Andy -- http://wingolog.org/
Re: Growable arrays?
On Sat, Jun 9, 2012 at 2:32 PM, David Kastrup d...@gnu.org wrote: Hi, the main data structure of Lua is a table, an associative array, and a table t has a continguous numerically addressed part from 1..#t, with all other indices going through a hashing mechanism. One principal distinguishing feature, like with a Scheme hashtable, is the ability to grow on-demand. Scheme/Guile vectors are fixed size. Now I have a situation where I have a basic type lattice with records stored in vectors, and this type lattice may be extended dynamically (which typically happens at the start of a whole file, for potentially multi-file runs). Scheme does not offer a suitable data structure for that. It is a bit of a nuisance that one can grow a hashtable efficiently and on-demand, but not so an array. Now it would be possible when the type lattice gets extended to store the new entries in a hashtable and go from there. Or put them into a list, and reallocate on first access beyond the existing element. That seems rather contorted. And since there is, if I remember, a project to run Lua on top of Guile, having a fundamental and reasonably efficient data structure corresponding to a Lua table, or at least the contiguous part of a Lua table, would seem like a reasonably useful idea. After all, there already _is_ such a mechanism underlying hash tables so it seems somewhat peculiar not to have it available for vectors as well. Suggestions? -- David Kastrup I don't know how much you know about data structures, and I must confess I'm not very educated on Guile or Luas implementations. Based on what you are writing I would assume that the scheme hashtables aren't growable in the same way as a vector has to be growable. The number of elements in a hashtable isn't limited by it's size. They are often implemented as each position (where the hashtables size is the number of positions) being a linked list giving the hashtable (in theory) limitless actual size. Growing a vector/array involves having to allocate new continuous memory and copying all the elements there, so for example in C++ (i think) the std:vector is increased by half it's current size each time meaning that the more expensive the copying gets the more elements you can insert into the vector before it has to resize. I would assume it wouldn't be that difficult to implement a pretty efficient growable vector for scheme. // Krister Svanlund
Re: subbytevectors
() Andy Wingo wi...@pobox.com () Sat, 09 Jun 2012 13:07:15 +0200 Again, the gain in expressiveness is probably worth it Overall, i am concerned about quick fixes and slow suffering in the Guile design. To break it down from different angles: Thinking positively: If you want to make a case for such a facility, why not show some code, both without (status quo) and with (proposed)? It should be clear what expressiveness is gained, and how. Thinking negatively: Guile 1.4.x has ‘make-shared-substring’, which is similar in spirit (since strings of that era are basically byte vectors), but i believe later Guile versions dropped that. It might be instructive to (reconstruct if necessary and) follow that chain of reasoning to avoid repeating a similar flip-flop. Thinking abstractly: IIRC, SRFI 13 suggests that its support for substrings would not be necessary if programmers wrote code using range style. Could the client code you have in mind be rephrased like that?
Re: subbytevectors
Hello, On Sat 09 Jun 2012 17:16, Thien-Thi Nguyen t...@gnuvola.org writes: If you want to make a case for such a facility, why not show some code, both without (status quo) and with (proposed)? It should be clear what expressiveness is gained, and how. For example, let's say I mmap a big file. (define x (mmap-file /usr/lib/debug/lib/x86_64-linux-gnu/libc-2.13.so)) I did some computation and have figured out that there is a region of interest between bytes 121241 and 121263 that interests me. I would like to be able to pass off that region to some other piece of code, without giving it access to the entire bytevector. I would also like to be able to pass around Guile 1.4.x has ‘make-shared-substring’ Guile 1.8, released in 2005, has substring/shared. So does Guile 2.0. IIRC -- and this was a long time ago -- Marius wanted to remove it, for ease of implementation, but users were using it, so he had to put it back in. Strings and bytevectors are fundamentally different, though. IIRC, SRFI 13 suggests that its support for substrings would not be necessary if programmers wrote code using range style. Could the client code you have in mind be rephrased like that? These are complementary strategies. Using ranges is usually more efficient, but more at times it is too cumbersome. Sometimes also you really want to restrict authority to only a certain window of the bytevector. For example, I am currently working on a problem that involves lots of work on a shared bytevector. I have to be careful to avoid printing out the bytevector because it takes a few seconds and trashes my terminal history. If I had subbytevectors, this wouldn't be as acute a problem. Andy -- http://wingolog.org/
Re: Growable arrays?
Krister Svanlund krister.svanl...@gmail.com writes: On Sat, Jun 9, 2012 at 2:32 PM, David Kastrup d...@gnu.org wrote: One principal distinguishing feature, like with a Scheme hashtable, is the ability to grow on-demand. Scheme/Guile vectors are fixed size. It is a bit of a nuisance that one can grow a hashtable efficiently and on-demand, but not so an array. After all, there already _is_ such a mechanism underlying hash tables so it seems somewhat peculiar not to have it available for vectors as well. I don't know how much you know about data structures, I do list the various implementations and details. and I must confess I'm not very educated on Guile or Luas implementations. And I do list the details here. Since I do it in free prose, chances are that I am not just quoting material I have not understood. Based on what you are writing I would assume that the scheme hashtables aren't growable in the same way as a vector has to be growable. I don't see anything supporting this assumption in what I wrote. Nor in Guile's documentation. 5.6.12 Hash Tables -- Hash tables are dictionaries which offer similar functionality as association lists: They provide a mapping from keys to values. The difference is that association lists need time linear in the size of elements when searching for entries, whereas hash tables can normally search in constant time. The drawback is that hash tables require a little bit more memory, and that you can not use the normal list procedures (*note Lists::) for working with them. Guile provides two types of hashtables. One is an abstract data type that can only be manipulated with the functions in this section. The other type is concrete: it uses a normal vector with alists as elements. The advantage of the abstract hash tables is that they will be automatically resized when they become too full or too empty. [...] 6.4.25.1 Creating hash tables . -- Scheme Procedure: make-hash-table [equal-proc hash-proc #:weak weakness start-size] Create and answer a new hash table with EQUAL-PROC as the equality function and HASH-PROC as the hashing function. [...] As a legacy of the time when Guile couldn't grow hash tables, START-SIZE is an optional integer argument that specifies the approximate starting size for the hash table, which will be rounded to an algorithmically-sounder number. The number of elements in a hashtable isn't limited by it's size. They are often implemented as each position (where the hashtables size is the number of positions) being a linked list giving the hashtable (in theory) limitless actual size. However, if the number of hash buckets is not grown along with the number of entries, hashtable access is O(n) in cost rather than O(1) since after the initial split into hash buckets, the cost is that of linear search. This is the difference in behavior between hashtables in Guile 1.4 (?) with fixed size, and hashtables in 1.6+ with variable size. Growing a vector/array involves having to allocate new continuous memory and copying all the elements there, so for example in C++ (i think) the std:vector is increased by half it's current size each time meaning that the more expensive the copying gets the more elements you can insert into the vector before it has to resize. Sure: since the growth happens with exponential backoff, the amortized cost for n entries is O(n). I would assume it wouldn't be that difficult to implement a pretty efficient growable vector for scheme. Since that already is what is used internally in hashtables it can't be difficult... The advantage of growing a hashtable is that you don't have waste: if you double the size of a hashtable, it means that you split each bucket in two, and potentially any bucket after the split can contain new data. In contrast, after a similar vector resize, half of the buckets are _guaranteed_ not to contain data. You can reduce the waste by using less than exponential backoff, but then the amortized cost is no longer O(n). Anyway: your answer was based on the assumption that I did not do my homework before asking, and that two people not reading documentation might guess better than one person not reading documentation. I hope I have now provided adequate coverage concerning this hypothesis so that it should be possible to focus on the smaller set of remaining ones. -- David Kastrup
progress with native code generation in guile
Hi, On linux, x86-64 I can now write, (use-modules (native aschm)) (define b (asm (inst mov rbx 10) ;rbx = 1000,000,000 loop: (inst cmp rbx 0) (inst jmp #:eq out:) (inst dec rbx) (inst jmp loop:) out: (inst mov rax 2) ; return value in register rax (inst pop rbx); we pushed the return adress before (inst jmp rbx))) ; jump back (mk-rwx b) ; Make the memory pages read write and ; execute (run-native b) ; run the code using a simple scheme And the code loops and return 0 (2). So it is possible to generate assembler from whithin guile and execute it which is pretty cool. If you have the right architecture, you can play with it at: https://gitorious.org/aschm Have fun Stefan
