Gpc July 2005

gpc@gnu.de

25 participants
67 discussions

Strings and Char Arrays
by Contestcen＠aol.com 21 Jul '05

21 Jul '05

> This SHOULD NOT work in BP or any flavor of Pascal, any more than the > following should work: > > const Digit: array[0..255] of 0..9 = 123456789101112; > > A string is a different data type than an array of char, with a lot of > different methods. > > I am surprised tht BP identifies short arrays of char with short strings. > > Would (and should) this work? > > program foo; > > var ch1, ch2, ch3: array[1..100] of char; > > begin > ch1 := '123'; > ch2 := '456'; > ch3 := ch1+ch2; (* or ch3 := Concat(ch1, ch2); *) >Writeln(ch3, ' ', Length(ch3)); > end. > > I say absolutely not. HF I tried this, and it does not compile. The Borland compiler will not allow ch1 := '123'; Assigning a string value to a character array is a shortcut for initializing character arrays so that you don't have to write Const ch: array[1..100] of char = ('H', 'e', 'l', 'l', 'o'); Instead you can write Const ch: array[1..100] of char = 'Hello'; However this works only in Const clauses, and only when the size of the array elements is less than 256 characters. If you need to initialize a character array greater than 255 chars in BP, you can resort to using absolute. For example Const ch1: array[1..5,1..100] of char = ('First 100 chars', 'Second 100 chars', ..., 'Last 100 chars'); Var ch: array[1..500] of char absolute ch1; Frank Rubin

3 2

Packing strings ()
by Contestcen＠aol.com 20 Jul '05

20 Jul '05

>> Making a perfect hash requires 7 additional tables, 3 independent hashes of >> the string, 3 tables to convert the hash values into summands, and one table to >> convert the sums into pointers to the strings. (There is a trick that can >> reduce this to 5 tables, but it makes the first hashing round slower.) > > Any references for these claims? > > gperf needs only one additional table. It doesn't need several > "hashing rounds", only one very short hash function. Did you > actually look at it (or comparable programs)? First, let me clarify some terms. There are two properties of hash functions involved here. The first is that every keyword hashes to a different value. This is called "collision-free" hashing, or "single-probe" hashing. The second property is that hash function for the N keywords is into a set of N things (such as N pointers, or the integers from 0 to N-1). This is called "minimal" hashing. If the hash function is both collision-free and minimal, then it is called "perfect." Apparently, perfect hashing is so hard to achieve in practice that the terms have become debased, and people are now calling a hash "perfect" if it possesses only the first of the two properties. When I made my statement about 5 or 7 tables, I had in mind my own implementation of perfect hashing (in the stricter sense). I invented this many years ago, possibly as early as 1980, but immediately (the next day, in fact) discovered that I was 2 or 3 years too late. It had already been published, I think in CACM. However, I do not have the reference. It is the only method I know to achieve (true) perfect hashing with large and diffcult keyword sets. I looked up the gperf program, and found that it satisfies the first property most of the time, except for large sets of keywords, and the second property rarely, only for small keyword sets. So, from my perspective, it does not achieve perfect hashing. Also, it appears to use 3 tables, not 1. In any case, we are getting off the subject, which was how to store a set of varying-length strings with minimal wasted space. The method that I suggested, using the Pascal Macro Compiler, uses no wasted space at all. I mentioned that an additional advantage is that its pointer table or index table could be arranged to provide O(log N) time searching without using any additional tables or space. The fact that this is not the fastest search method is beyond the scope of this discussion. If a practical method for searching the table in minimal time is required, then a self-expanding hash function would be a more suitable solution, since these can be built during runtime in linear time, with moderate wasted space. Frank Rubin

4 4

Re: Packed strings
by Frank Heckenbach 20 Jul '05

20 Jul '05

Contestcen(a)aol.com wrote: > Yes, it is getting boring repeating that storage management and data access > are independent issues. No, they aren't. > I can't think of any standard access method where the > choice of any standard storage management technique adds more than a single > table reference to the process of retrieving a string. Which is already one thing that you may or may not save. I mentioned alignment several times. > I am starting to think that there is some problem in terminology that is > keeping us from agreeing on this point. Maybe, if you can give me an example of a > standard access method, and two different storage management methods that > have a large difference in how long it takes to retrieve a keyword, then that > might reveal some difference in our language or in our assumptions. ad 1, you might want to string in a tree structure, or a pointer. That's one access and a pointer more to store. ad 2, if the string is unaligned, you have to copy it before you can use it, which I think is a substantial difference, both in time and in (code) size. Frank -- Frank Heckenbach, frank(a)g-n-u.de http://fjf.gnu.de/ GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)

1 0

Re: Array elements as control variables
by Frank Heckenbach 20 Jul '05

20 Jul '05

Contestcen(a)aol.com wrote: > >> Using array elements as control variables is very useful when you want the > >> ability to stop a deeply nested loop, checkpoint the program, and then > resume > >> the execution from the same point later. I would not like to see this > >> capability removed. > > > > As first glance, since only constant indices are allowed, it would > > seem to be equivalent to using a1, a2, ... instead of a[1], a[2], or > > am I missing something? > > > > Can you give an example for the situation you describe? > > The essential difference between using a1, a2, ... and a[1], a[2], ... is > that I can write loops that do something useful with the a[i] elements. For > example, suppose that I have the statements > > if KeyPressed > then begin > CheckPoint (depth); > exit; > end; > > located at various places in a deeply nested loop. Here depth indicates how > deep in the nest the checkpoint was taken. Now I can put the following inside > the CheckPoint procedure. > > for n := 1 to depth do > writeln (checkfile, a[n]); > > This will write out all of the known control variable values. The restart > procedure can do this > > depth := 0; > while not eof(checkfile) do begin > depth := depth + 1; > readln (checkfile, start[depth]); > end; > for n := depth+1 to maxdepth do > start[n] := 1; {or whatever the lower value is} > > Then in each loop in the nest the control variable can be tested like this > > for a[10] := 1 to max[10] do begin > eq := true; > for n := 1 to 9 do > if a[n] <> start[n] > then eq := false; > if eq and (a[10] < start[10]) > then continue; > ... > end; > > If you did not have the ability to use array elements as control variables, > then the previous code would have to be the verbose > > for a10 := 1 to max10 do begin > if (a1 = start[1]) and (a2 = start[2]) and (a3 = start[3]) and (a4 = > start[4]) and (a5 = start[5]) and (a6 = start[6]) > and (a7 = start[7]) and (a8 = start[8]) and (a9 = start[9]) and (a10 < > start[10]) > then continue; > end; > > Yes, it can be done, but I much prefer the loop version to the last version. Can't you use a macro processor to generate the verbose code? ;-) Anyway, I see that this is an example, at least in theory. However, I'd probably do it differently in practice. I think this is more efficient, since you don't need any comparisons, and in particular no extra code in the innermost loop which is the most time-critical. If you need the original start values afterwards, copy the array before the first loop, of course. for a1 := start[1] to max[1] do begin for a2 := start[2] to max[2] do begin for a3 := start[3] to max[3] do begin ... end; start[3] := 1 end; start[2] := 1 end; Frank -- Frank Heckenbach, frank(a)g-n-u.de http://fjf.gnu.de/ GnuPG and PGP keys: http://fjf.gnu.de/plan (7977168E)

1 0

Packing strings ()
by Contestcen＠aol.com 20 Jul '05

20 Jul '05

>>> This assumes that you know precisely what the compiler is doing with >>> your macros, and that compiler optimisations do not achieve better >>> results than what you have hand-coded. [The Chief] >> >> This may be true for executable code generated by the Pascal Macro Compiler, >> but it is not true for the data declarations that are generated for the packed >> strings. There is no executable code involved, so the compiler has nothing >> to optimize. [Rubin] > > Yes -- if you only store the data and never access them. > > Most people actually want to use the data they store. And the layout > of the data can easily affect the code necessary to access it, both > in speed and size. [Hockenbach] The Pascal Macro Compiler could certainly generate code for accessing the strings, however the Keyword String macros do not generate access code; they generate data structures. These structures are well-suited for access by hash functions, hash trees, binary trees, heap search, or binary search. The normal code and tables for these methods will work with minimal, or no, complications. In the last two cases, no extra storage or structures are needed. Frank Rubin

2 1

sysutils unit
by Silvio a Beccara 19 Jul '05

19 Jul '05

Hi everybody, and particularly the African Chief, I'd need a version of the sysutils unit which compiles with the latest snapshot of GPC (20050331). I managed to compile GPC, but the older version of sysutils (used quite extensively throughout my codes) I have doesn't work with it, and the website for the download of contributed units is not available. Thanks in advance, best regards Silvio a Beccara - Trieste, Italy -- Email.it, the professional e-mail, gratis per te: http://www.email.it/f Sponsor: Hai una fotocamera digitale e vuoi stampare le tue immagini * su vera carta fotografica professionale? Clicca qui: http://adv.email.it/cgi-bin/foclick.cgi?mid=1533&d=19-7

2 1

Packing strings ()
by Contestcen＠aol.com 18 Jul '05

18 Jul '05

>>There is no wasted space, so there is nothing that can be improved. > > Do you compress the strings (e.g. LZW) or are you just packing them efficiently? My understanding from the original post is that he wanted the strings stored as given, not compressed. The macros simply store the strings end-to-end without any gaps. However, the macros would work equally for compressed strings, assuming they have the same form, namely length field and data string. If you want the entire body of strings compressed as a unit, then you could use the macros to create the concatenation of all the individual strings, and compress the result. It would be up to you to devise methods for accessing the strings within the compressed mass. Frank Rubin

2 1

Pascal Macro Compiler
by Contestcen＠aol.com 17 Jul '05

17 Jul '05

> NO, YOU, DON'T! > > People have been telling you this all the time, why don't you > listen? THIS DOES WORK IN BP: > > program foo; > const > ch: array[1..100] of char = 'When in'; > begin > end. > > (It doesn't work with 1000 indeed, as BP has a string length > limitation of 255, but that's just a BP quirk.) That's very nice. However, please recall that I said the main reason for using a character array instead of a string is because I needed more than 255 characters. So, having a better way to initialize a character array of up to 255 characters doesn't help me. If I only wanted 255 characters I would have used a string in the first place. You may call this "just a BP quirk" but when you are using BP, or when you want to be compatible with BP it is not a "quirk" it is a real limitation. I have to assume that some of the users of the Pascal Macro Compiler will be using BP, regardless of whatever else exists.

3 3

Misfeatures in For loops
by Contestcen＠aol.com 17 Jul '05

17 Jul '05

>> GPC accepts the following program, but produces quite silly results: >> >> program Foo; >> >> var >> a: array [1 .. 2] of Integer value (0, 0); >> i: Integer; >> >> begin >> i := 1; >> for a[i] := 1 to 10 do >> begin >> WriteLn (i, ' ', a[i]); >> if a[i] = 5 then i := 2 >> end >> end. >> >> The problem is that it evaluates the index i each time, not once >> before the loop. It would be possible to fix it, but do we really >> want that? Neither BP nor CP/EP allow it, they allow only >> identifiers in for-loops. >> >> Waldek and I see no need for such a feature. > > Neither do I. > > Nor I. I vaguely recall that it is forbidden in at least ISO 7185, > but cannot quote chapter and verse. This is a milestone, where BP > is more standards adherent :=) I have come in late to this discussion, and I am not sure what is the supposed "misfeature." Are the participants saying that Borland Pascal does not accept an array element as the control variable of a For loop, and that therefore GPC should not accept array elements either? If that is the case, then the premise is incorrect. BP does accept array elements as control variables. The following program compiles and runs correctly in BP. It produces the expected result 100.000. Program Try; Var a: array[1..10] of integer; s: real; Begin {Try} s := 0.0; for a[1] := 1 to 10 do for a[2] := 1 to 10 do s := s + 1.0; writeln (s:10:3); End. {Try} Using array elements as control variables is very useful when you want the ability to stop a deeply nested loop, checkpoint the program, and then resume the execution from the same point later. I would not like to see this capability removed. Frank Rubin

2 1

Packed strings ()
by Contestcen＠aol.com 17 Jul '05

17 Jul '05

>> If the strings are not known until run time, the most >> efficient way is to allocate a large block of storage, and move the >> strings in end-to-end, using a separate array to hold either pointers or >> indices into the large block. >> >> When the block is full, allocate another large block using New. There >> are two ways to manage the storage. (1) Extension block method: Use a >> second array to point to the set of large blocks. Each string will be >> accessed using two pointers or two indices. The first will point to the >> particular block, and the second will point to the string within the >> block. (2) Single block method: Make the new block twice as large as >> the previous block, move the existing strings into the new block and >> then Dispose the old block. > > Very convoluted. A linked list or string collection would do just fine. In my earlier response to this post, I should have asked how you allocated storage for that linked list or string collection. My suggestions deal mainly with storage allocation. Within the blocks you could choose to have a linked lis or a tree structure if you so chose. As I have pointed out before, storage management and data access are separate issues. Frank Rubin

2 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

2000

1999

1998

1997

1996

1995

Gpc July 2005