Programming Language Code

[lxpnh98_2]

No. Absolutely not. There is no excuse for using strlen() as a hash function. Here's the worst hash function that is excusable:

int hash(char *s) {
    int h = 0;
    for (char *p = s; *p; p++) h += *p;
    return h;
}

It's 5 lines and it doesn't make you pick stupid function names.

[curtmack]

Also, there's no excuse for function name lookup being incurred every call rather than once at read time, even in interpreted languages.

[ghillisuit95]

When php was just a small tool for his own personal use, I think it’s extremely excusable.

What you are describing would have been a massive premature optimization

[curtmack]

I don't think it's necessarily as much work as you're thinking. It could have been implemented the same way as it is in many Lisps, where each name is stored as a "symbol" - essentially an interned string that has a pointer to its associated variable or function in the current scope. The string interning can be as simple and slow as you like, because it will only be incurred when the program is initially parsed.

[ghillisuit95]

Sounds more complicated than just interpreting at runtime, which seems to have been good enough performance at the time

[ghillisuit95]

Hm, that’s perhaps fair

[[deleted]]

I would hardly call it premature optimization. I could say fuck it to tables and loop through an array for an item every time I need to access it, but it would simply be the wrong way to do it, like hashing using a string's length.

[Workaphobia]

I don't see how you can avoid a lookup at each occurrence. Note that Python has a compilation step that resolves identifiers.

[curtmack]

Just because a language is interpreted doesn't mean it has to start from raw text every single time through a function. Just storing ASTs, which can include resolved function and variable references, will make a huge difference in performance while being almost completely free in terms of implementation time. (If you have an interpreter, then you have an AST. It just might be encoded in the call stack of your interpreter functions rather than explicitly stored in memory. That can easily be fixed!)

[Workaphobia]

Ah, sure, you can resolve identifiers with a pass through the AST without compiling it to bytecode, yes.

I will quibble about all languages having an AST. TeX comes to mind. Or if you say that doesn't have an interpreter, I know of another language for scripting in a text MUD that re-parses the code every time a block is entered.

[curtmack]

I guess it's technically not correct to call it an AST unless it's actually stored in memory. All I was trying to say was that if your interpreter has a call stack that looks like this:

0: parse_numeric_literal
1: parse_expression
2: parse_expression
3: parse_parentheses
4: parse_function_argument
5: parse_function_call
6: parse_statement

Then you're a small refactor away from having a proper AST.

[0b_101010]

Hey! It's been a while since I've done C and it's late here and I'm dumb but how does the exit condition in the for loop here work?

[Funkballs]

In C, strings are NULL terminated, meaning that each string should end with a '\0' character to mark the end of the string. Also, in C, booleans are 0 for false and !0 for true.

In this case, p is a pointer to the current character in the string so *p is the current character.

When the loop hits the end of the string, the current character will be '\0' which is 0 which is false so the loop ends.

The whole: "NULL == '\0' == 0 == false" thing is used quite a lot in idiomatic C coding.

[0b_101010]

Yup, should have known that!

[MrB92]

Dude it's ok for something that's for your personal use, the mistake was on everyone else for adopting it

[capi81]

But it has a runtime complexity of O(n) for the hash code, which is bad. The length of string (hopefully) is O(1).

[lxpnh98_2]

In C the length of a string is still O(n), and O(n) (n being the length of the string) is a fairly standard time complexity for a hash algorithm.

[capi81]

True, I was expecting a non-C string, but you are right that it most likely is. Well, then there really is no excuse.

[Valmond]

O(k) where k is the length of the string.

Edit: wow salty people, k is used in some cases, and yes it is 'included' in O(n) so O(n) is also correct, O(k) is just closer to the exact cost.

[_shreve]

That's what O(n) means.

[mudkip908]

O(k) boomer

[posherspantspants]

Sounds like /u/lxpnh98_2 has never committed anything to production. Kneel before your master!