Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.

Due to spam on this forum, all posts now need moderator approval.

 Entire forum ➜ MUSHclient ➜ General ➜ How do I make an Autocleric?
How do I make an Autocleric?

It is now over 60 days since the last post. This thread is closed.     Refresh page

Pages: 1  2 3  

Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #15 on Thu 01 Mar 2007 05:35 AM (UTC)
Message
Quote:

Lua doesn't start arrays with 0 either ...


That is true, and is another catch for C programmers. Personally I quite like it, as you can use 1 for the first position in a string, and -1 for the last position, which makes sense to me.

I also think counting from 1 is more natural in real life, and bearing in mind Lua was designed as a scripting language, and not a mathematical language.

People do stuff like:


  1. Say "He is number 1 in his class!" (not number 0)
  2. Say "I will have the first turn" (not the zero'th turn)
  3. They number lists (like this), from 1.


I acknowledge there are arguments to be made for numbering from zero, so please don't do dozens of posts proving me wrong. There is something to be said for both sides of the argument, and this argument has been pursued on the Lua wiki as well, at some length. :)

For more information, see this:

http://lua-users.org/wiki/CountingFromOne

My thoughts appear there as well. ;-)
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Shadowfyr   USA  (1,790 posts)  Bio
Date Reply #16 on Thu 01 Mar 2007 06:48 AM (UTC)
Message
Well, the only real argument is basically one that programatically the engine has to subtract one *then* start indexing things in memory. Its like what.. a few clock cycles? Maybe if we still coded for 1mhz 8086 processors it would be hugely critical. lol
Top
Posted by Shaun Biggs   USA  (644 posts)  Bio
Date Reply #17 on Thu 01 Mar 2007 06:52 AM (UTC)

Amended on Thu 01 Mar 2007 07:18 PM (UTC) by Nick Gammon

Message
Quote:
That is true, and is another catch for C programmers. Personally I quite like it, as you can use 1 for the first position in a string, and -1 for the last position, which makes sense to me.

I think it makes sense to most people as well, I'm just so used to counting from 0 on a computer that I get snagged every now and again. I personally don't care either way, so long as I can remember which I'm using. Otherwise, I just don't notice the error for a while until I realize what language I'm using.

Quote:
I acknowledge there are arguments to be made for numbering from zero, so please don't do dozens of posts proving me wrong. There is something to be said for both sides of the argument, and this argument has been pursued on the Lua wiki as well, at some length.

This was not my intention, I was just using that as an example of how Lua is different from languages with which I am more familiar.

Quote:
You also have to be careful in Lua, that 0 is considered true, as the manual warns.

Also fell into that trap a while ago while converting a script for MC from jscript into Lua... I had only been using the language for a day or so. Again solved with me doing a painfully simple test to find out I fell victim to thinking things worked a certain way before looking them up. Fortunately, I've been poking a friend who has been helping me out when I get stuck, and I've had to respond to most of the solutions with "Oh, that was simple." I really do like the language. They combined simple and powerful quite well.
It is much easier to fight for one's ideals than to live up to them.
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #18 on Thu 01 Mar 2007 07:18 AM (UTC)
Message
Quote:
To say "is it true it is raining?" is a bit redundant (except for emphasis perhaps).
Well, that's my point. :-) I like to include it when I want to emphasize something. Of course I very often omit it, but occasionally when the context might not be perfectly clear I include it. And as I said, I think it makes more sense when you are speaking of the "false" case.

If I ask you, "is it not raining", I expect to hear "yes" if and only if it is not raining. If you don't know, that is, if your "value" for the proposition "raining" is "nil", I do not expect you to say yes. Rather I would expect something like "I don't know".

Of course in programming it is very convenient to have nil be the same as false for conditions. Nonetheless I think it's important to always, always remember that they are not the same thing. For instance, t = {}; t.foo = "bar"; t.foo = nil is quite different from assigning false to t.foo.

I think though that what we're saying is not fundamentally that different. I may have exaggerated my position somewhat; I certainly don't always throw in the == true. I only use it when for whatever reason it makes things clearer to me.

Quote:
Well, the only real argument is basically one that programatically the engine has to subtract one *then* start indexing things in memory. Its like what.. a few clock cycles? Maybe if we still coded for 1mhz 8086 processors it would be hugely critical. lol
I'm not sure this is an issue. It depends on how tables and arrays are implemented, I suppose.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Shadowfyr   USA  (1,790 posts)  Bio
Date Reply #19 on Thu 01 Mar 2007 07:23 PM (UTC)
Message
Your kidding me right? It has nothing to do with how tables or arrays are "implimented". Its just basic machine logic. If you have a block of say integer values:

300: AB CD 1D 34 5F DD 00 00

The code to get them is "on the machine level" going to look like:

ldx #0000
1:lda 0300, x
jsr <some place you do something with the number>
cmp #0000
inx
bne 1:
rts

This is true even if you are retrieving text strings. Unless you intentionally leave the first index location of your data structure empty, at some point your engine or code has to subtract 1 from the value, to get back the "correct" memory location to start retrieving the data. Otherwise you have areas in memory that are wasted, because processors "all" start with 0 as the first offset location for retrieving data from memory.

Dang modern programmers.. Don't know a damn thing about how the machine actually works... ;) lol
Top
Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #20 on Thu 01 Mar 2007 07:24 PM (UTC)
Message
Quote:

Nonetheless I think it's important to always, always remember that they are not the same thing.


I agree with this, the principle being the same as SQL where NULL represents "no data", even in a case of a boolean field, where the other values can be true or false.

Conceptually it is very useful to be able to say "nil means no data". Take for example, the question:

"Is David going to the party?"

Possible answers are:


  • Yes (true)
  • No (false)
  • Don't know (nil)


We could conceivably scan our table here and contact each person in our list for whom we have a "don't know" and attempt to convert it into "yes" or "no", so we can be sure how many people are attending.

For such an operation, distinguishing "don't know" (nil) from "no" (false) is obviously important.

On the other hand, to count how many people are attending the party (as far as we know), then a simple test for "anything that is not 'no' or 'nil'" gives us the answer. This is effectively what the Lua "if" test does.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #21 on Thu 01 Mar 2007 07:32 PM (UTC)
Message
Quote:

Your kidding me right? It has nothing to do with how tables or arrays are "implimented". Its just basic machine logic.


No, I'm afraid he is not. Initially Lua implemented tables purely as hash-table lookups. In other words, the entry for [0] is a hash of 0, the entry for [1] is a hash of 1, and so on.

In fact in Lua there is absolutely no objection to having a negative index. Take for example:


t = {}

t [-5] = "Nick"
t [-10] = "Gammon"

table.foreach (t, print)

Output

-5 Nick
-10 Gammon


Now if they were using machine code to index into an array, as you suggested, then the negative entries would index out of the bounds of the table.

Thus, in early versions, the time taken to access any entry would be constant, that is the time needed to convert the subscript into a hash, and find it in the table. They could have started tables at 100, and not made any difference.

However in more modern versions of Lua (maybe 4 onwards), they have made table access more efficient by making tables internally have two parts - a hash part and a numeric part. Thus a table consisting of only subscripts 1 to 10 would fall entirely in the numeric part. If you added a subscript "x", or a large or negative number, then that goes into the hash part.

I think you would find that all this logic, like seeing what range the subscript is in, hashing it, and so on, would totally swamp any considerations (in CPU cycles) of whether you start at 0 or 1.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Shadowfyr   USA  (1,790 posts)  Bio
Date Reply #22 on Thu 01 Mar 2007 07:58 PM (UTC)
Message
Probably true, though, on the machine code level, its still starting with 0. You're just basically saying that the system they use in Lua has that 0 in some place that may be 500 addresses "before" the place currently being used in what ever buffer they created to hash the table. In which case, your 1 isn't even a one, its a numeric lookup to a memory address, in which case, it might as well be a, b, c, d, e, etc, for all that the actually value matters (mind you, numbers tending to be way more useful. lol)
Top
Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #23 on Thu 01 Mar 2007 08:31 PM (UTC)
Message
Quote:

... on the machine code level, its still starting with 0 ...


I think this is a matter of definition, a bit. Say I have a table like this:


t = {}
t ["nick"] = 10
t ["gammon"] = 20

table.foreach (t, print)


The keys are "nick" and "gammon". Which one does the table "start" with? It actually prints "gammon / nick" when I run it, so I suppose you can say it "starts" with gammon, but I think this is an idiosyncracy of the hashing algorithm.

The fact is, that in Lua (and various other constructs, for example some container types in STL), there is no linear array, and therefore no "first" entry in the classical sense (that is, the sense of "index by zero").

If you make a linked list in C, the first entry is the first item in the list, but in terms of memory storage, may be occupying a higher memory address than subsequent items.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by Nick Gammon   Australia  (23,133 posts)  Bio   Forum Administrator
Date Reply #24 on Thu 01 Mar 2007 08:37 PM (UTC)
Message
Quote:

Lua doesn't start arrays with 0 either ...


Following on from this, really Lua doesn't start arrays anywhere in particular, as I have shown, you can have negative subscripts.

It is probably more accurate to say that some Lua table access functions, for example table.foreachi, and the ipairs function, work by accessing item 1 onwards in a table, even if other values (like 0, -10, -2343) exist.

They are defined to do that, in other words, the function does that by definition, not because the table "starts at one".

Here is an excerpt from the Lua reference manual (see http://www.lua.org/manual/5.1/manual.html#5.1):


ipairs (t)

Returns three values: an iterator function, the table t, and 0, so that the construction

     for i,v in ipairs(t) do body end

will iterate over the pairs (1,t[1]), (2,t[2]), ···, up to the first integer key absent from the table.


The ipairs function does not claim to start at the "start of" the table, but simple starts at index 1, and so on, until it finds a missing integer key.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #25 on Thu 01 Mar 2007 10:41 PM (UTC)
Message
Quote:
Dang modern programmers.. Don't know a damn thing about how the machine actually works... ;) lol
Dang newbies, don't know a damn thing about how languages are actually implemented internally or any of the formal reasoning for why things work the way they do. *wry smile*

Nick has started explaining this and I will explain it some more. If your array is implemented as a hash table, then the key is for all intents and purposes not a number, even if it is "0" or "1" etc.

The implementation of a hash table will convert your key, using some magic, to a hash value. That hash value will then give you the bucket of the hash table. For simplicity's sake we will assume that there are no collisions in the hash table.

Now, there is no guarantee that the bucket assigned to key "1" by the hash table is the number "1" or "0" or any such thing. For all you know the bucket could be 792.

So, starting your array by zero or one makes absolutely no difference in terms of performance from the Lua programmer's side. You still have to go through the hash function in C, which will convert the key to a bucket. The bucket, of course, is a memory address, which can then be dereferenced immediately.

Therefore, I maintain my original statement and refute your response.

Your mistake is to have not understood the difference between a language's semantics, its implementation in some programming language e.g. C, and finally the machine code underlying it all. You did not realize that the implementation of a data structure can change, sometimes dramatically, the procedure to look up a given key. And finally I think you did not sufficiently mark the difference between a table key and an index into memory. The two are quite different, especially in a higher-level language like Lua the intention of which is to remove oneself from implementation details and establish a formal semantics independent of machine-level specifics.

And finally, I think you were a little premature in your supposition that I know nothing about how things actually work at the machine level. :-) Writing some stuff in hex and assembly doesn't necessarily make your point any better, especially when by focusing on the leaf, you missed the tree, much less the whole forest, as it were.



Besides, as Nick pointed out, even if you were translating numbers to indices -- as Lua does for the special part of the table that Nick mentioned -- the cost of subtracting one from a number is, for almost everybody and for almost all purposes, completely irrelevant when compared to other costs. I can think of rather few cases when you would actually care about squeezing every last machine instruction's worth of time out of your program, and in most of those cases, you would be somewhat silly to be doing it in Lua to begin with.



Anyhow. Enough of that (for now at least).
Quote:
On the other hand, to count how many people are attending the party (as far as we know), then a simple test for "anything that is not 'no' or 'nil'" gives us the answer. This is effectively what the Lua "if" test does.


That's a very good point Nick. It's true that in almost all cases, a value of "I don't know" is basically the same as "not yes". And usually, that is what we want. What it comes down to is the nature of the question asked.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Shadowfyr   USA  (1,790 posts)  Bio
Date Reply #26 on Fri 02 Mar 2007 09:17 AM (UTC)
Message
You don't need to explain it more. As I said in my own later post, in cases where you are using hash systems, the index is just a place holder. If its numeric you can, in theory, get a ordered list out of it. But it could just as easilly be colors, sizes, types of bugs, or some sequence of letters, like a-z, aa-az, ba-bz, etc. The "starting" symbol is completely irrelevant.

What I meant about the machine level stuff is "linear" tables, where the index is some specific number of records from the "start" of the memory its sitting in. Most languages tend to require, even with strings, which often have fixed limits on there allowed length, that the discrete "chunks" be a known size, so that the index number is "actually" a multiplier to the linear location of the *actual* memory address of the data. In other words, while ones like Lua uses hashes, because they are more efficient in some ways at storage, though maybe more costly in terms of some overhead, (a bit enough hash will be bigger than the processor can keep in its L1 or L2 caches for fast retrieval, for example), most languages have not used liked lists or hashes for arrays, but instead structured them like:

0000: [data chunk #1, fixed size, two bytes]
0002: [data chunk #2, fixed size, two bytes]
0004: [data chunk #3, fixed size, two bytes]
0006: [data chunk #4, fixed size, two bytes]

The location is literally n * 2 bytes into the arrays memory in such cases. The 3 position is either actually #4, or its (n-1) * 2, depending on if you use 1 or 0 to start the indexing.

See, all anyone had to do, which Nick did quite handilly, is explain that a hash was being used, not a linear address space. I freely admit I didn't know the implimentation differed from what "most" languages consider to be "arrays". So sue me. Your extra explanations was hardly necessary though, nor was the email I got from Shaun, which also covered the same thing. BTW, how are you supposed to correctly reply to those, since the dang things reply address ends up being the "forum" instead of the senders?

Oh, and I am well aware of what linked lists are too. I tried, unsuccessfully, one time to make one that could be both sorted and randomized at the same time. I strongly suspect that the useless Pascal compiler I was using was taking up too much memory on the machine and the 64k limit on the old Apple IIs was only compounding the problem. It *ran*, but large parts of the list got "lost" somehow... Wasn't my best success story. lol
Top
Posted by David Haley   USA  (3,881 posts)  Bio
Date Reply #27 on Fri 02 Mar 2007 10:20 AM (UTC)
Message
Quote:
Most languages tend to require, even with strings, which often have fixed limits on there allowed length, that the discrete "chunks" be a known size, so that the index number is "actually" a multiplier to the linear location of the *actual* memory address of the data.
You are compounding high-level language semantics and implementation details. C or assembly working a certain way means next to nothing about how other languages present the data to you and what they require chunks or what-have-you to look like.

I don't understand how can you make claims about what "most languages [...] require" when you only know a few small number to begin with (and not the most representative languages, to boot) much less implementation details of e.g. interpreted languages. It's like your claim about "most languages" considering it an error to have expressions as statements. You really shouldn't go out on limbs like that...

Quote:
I freely admit I didn't know the implimentation differed from what "most" languages consider to be "arrays". So sue me.
Well, I'm not sure what basis you have to be making claims about "most" languages to begin with... so yes, I will in fact sue you. :-) You have a tendency to make claims about things outside the scope of what you truly know, if you don't mind me saying so.

Quote:
In other words, while ones like Lua uses hashes, because they are more efficient in some ways at storage,
Hashes are not used for storage efficiency. In fact they are not necessarily the most storage-efficient data structure! Hashes are used for the extremely fast look-up time. (Of course, assuming that your hashing algorithm is good, and that you have enough buckets and/or few enough elements to avoid collision.)

Quote:
BTW, how are you supposed to correctly reply to those, since the dang things reply address ends up being the "forum" instead of the senders?
I thought those emails had as a return value the sender's email address; at least, the ones I received did. In any case you can probably just use the forum's email facility to send an email back, if you care to do so.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
Top
Posted by Shaun Biggs   USA  (644 posts)  Bio
Date Reply #28 on Fri 02 Mar 2007 06:06 PM (UTC)

Amended on Fri 02 Mar 2007 07:44 PM (UTC) by Nick Gammon

Message
Quote:
Your extra explanations was hardly necessary though, nor was the email I got from Shaun, which also covered the same thing. BTW, how are you supposed to correctly reply to those, since the dang things reply address ends up being the "forum" instead of the senders?

There is a spot if you click on someone's name which says "Send an email to _____" which is what I used to email you in the first place. Sorry about dealing with things like that, but I was trying to avoid this whole thread, as I said in the email. Nick said he didn't want the whole 0 vs. 1 thing cluttering up his boards when there was already a link to a very long discussion on Lua's site.

Quote:
Oh, and I am well aware of what linked lists are too. I tried, unsuccessfully, one time to make one that could be both sorted and randomized at the same time. I strongly suspect that the useless Pascal compiler I was using was taking up too much memory on the machine and the 64k limit on the old Apple IIs was only compounding the problem. It *ran*, but large parts of the list got "lost" somehow... Wasn't my best success story. lol

I did the same in Pascal during high school on my 286.. how I miss that 12mhz and a whole meg of ram and HUGE 40 mb hard drive. Anyway, I wound up having to make a doubled list. I had the data, the next and previous. Then a record that contained the id and the next and previous for that set. It worked really well until I attempted to delete something, where it would reboot my computer. I never could figure out where I was going wrong.

As for the 64k limit, I believe that was a Pascal issue. Pascal was designed as a teaching language, and has a few oddities because of that. If I remember right, there was a limit in how large a source file could be. You simply have to break your code up into smaller files. I forget what that the syntax for that is, but when you want to access the extra file, you put it in your Uses section. Doing that, I made a game based around the doors game "the Pit" for my CS final my senior year which took up around 150k of source, and then several data files. Had I actually known known some of the things I know, it would probably have been about half that size.
It is much easier to fight for one's ideals than to live up to them.
Top
Posted by Shadowfyr   USA  (1,790 posts)  Bio
Date Reply #29 on Fri 02 Mar 2007 07:09 PM (UTC)
Message
Actually, I think I got it wrong. It wasn't 64k, but... Well, it had to do with the limitations of the hardware. Each "bank" was only 0000-FFFF, or "640k", but you generally only really had access to one bank of the two, and a number of memory sections where dedicated to video display, the stack, the softswitches used to control the hardware and the permanent ROM functions. That left you with 3-4 usable "sections", non-connected with each other, none of them bigger than about maybe 300k? And some of that space had to be taken up by the debugger and reload code for the Pascal system when you exited your application.

As for hashes. Sorry, partly meant lookup speed, but also the fact that, while sections of memory might go unused, the chunks don't "necessarilly", I assume, need to be fixed sizes, so you use "less" space for data that doesn't need fixed sizes in it. Unless I am completely wrong about that. Needing to pre-allocate something like 200 strings, all of them 255 bytes in length, because you can't just store the lookup address (and maybe length), then use only the space needed to store *that* specific string.... Gets rather inefficient in terms of memory use. Though, I admit I don't know if hashes help to solve that problem or not, but it just seems reasonable that, to save on space, you could/would do something like that.
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

93,279 views.

This is page 2, subject is 3 pages long:  [Previous page]  1  2 3  [Next page]

It is now over 60 days since the last post. This thread is closed.     Refresh page

Go to topic:           Search the forum

[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.

Home